Introduction to Logic (‘Methodenkurs Logik’) Winter term 2014-2015 Mondays 2:30--4:00pm @ 2321.HS 3H INSTRUCTOR Todor Koev (Todor.Koev@uni-duesseldorf.de) Propositional logic: semantics Logical translations Truth tables Working with truth tables Special formulas: contingencies, tautologies, contradictions Syntax of propositional logic We now know how (well-formed) formulas of propositional are constructed. We know that roughly: o p o pq o pq o pq o p q means means means means means ‘it’s not the case that p’ ‘p and q’ ‘p or q’ ‘if p, then q’ ‘p just when q’ We can then translate back and forth between English and propositional logic. Logical translations I Translating English into propositional logic: (1) Jay Z is cool. p translation key: p = ‘Jay Z is cool’ pq (2) Jay Z is cool and Kim K is annoying. translation key: p = ‘Jay Z is cool’, q = ‘Kim K is annoying’ (3) If I don’t kiss Sarah Dingens, I’ll cry. p q translation key: p = ‘I kiss Sarah Dingens’, q = ‘I’ll cry’ Hint: Try to represent in the propositional logic formula all logical connectives found in the English sentence. Logical translations II (4) The engine is not noisy and it does not use a lot of gas. translation key: p = ‘the engine is noisy’, q = ‘the engine uses a lot of gas’ p q (5) Nobody laughed or applauded. translation key 1: p = ‘nobody laughed’, q = ‘nobody applauded’ p q (Q: Anything funny about this translation?) translation key 2: p = ‘somebody laughed’, q = ‘somebody applauded’ ( p q ) Language and the Mind Gottfried Leibniz (1646-1706) envisaged creating an artificial “universal language” which represents concepts/ideas and provides logical rules for their valid manipulation. Natural languages stand for complex, or derivative, concepts that can be reduced to simpler concepts. “…when there are disputes among persons, we can simply say: Let us calculate, without further ado, and see who is right.” (G. Leibniz) Truth tables Truth tables are an easy way of determining the truth value of a complex formula from the truth values of its immediate parts and the connective that connects those parts. (It is assumed that each sentence is true or false.) Truth tables thus obey the Principle of Compositionality! There is a truth table for each connective. Truth tables can be regarded as providing the meaning of propositional connectives (i.e., negation, conjunction, disjunction, implication, and equivalence). Negation 1 0 0 1 If the first sentence is true/false, then the second sentence is false/true. (6) People in Düsseldorf are friendly. (7) People in Düsseldorf are not friendly. Potential issues: “Metalinguistic” negation can negate any feature of a sentence: (8) He doesn’t eat pot[a]toes. He eats pot[ej]toes. (9) He is not smart. He is a genius! Conjunction 1 1 0 0 1 0 1 0 1 0 0 0 The following sentence is true only if both parts are true. (10) Jay Z is cool and Kim K is annoying. Potential issues: (11) She got married and got pregnant. ≠ She got pregnant and got married. (12) He has rich parents but he doesn’t have any money. (13) Faruk traveled to Istanbul. He has family there. Disjunction 1 1 0 0 1 0 1 0 1 1 1 0 The following sentence is true as long as one part of it is true. (14) Jay Z is cool or Kim K is annoying. Potential issue: English ‘or’ may be exclusive, i.e. require that is false when both and are true. (15) He is either in Paris or (he is) in Berlin. (16) He is in Paris or (he is) in Berlin. Implication 1 1 0 0 1 0 1 0 1 0 1 1 The conditional sentence below is false only when the antecedent (=the if-clause) is true and the consequent is false. (17) If Hans passed the exam, he will happy. Problem: Counterfactual conditionals are incorrectly predicted to be always true because the antecedent is false. (18) If I was a millionaire, I would stop teaching logic. Our ‘material’ implication doesn’t say much about counterfactual sents. Equivalence 1 1 0 0 1 0 1 0 1 0 0 1 An equivalence is true when the two formulas have the same truth value: both are true or both are false. (19) I’ll go out (if and) only if you do the dishes. Working with truth tables 1 Truth tables derive the truth value of a complex formula from the truth values of the atomic parts. We consider all possible combinations of truth values assigned to atomic sentences and derive We only need to know how the formula was constructed. For this purpose, we first draw the construction tree. Working with truth tables 2 Example: Provide a truth table for the formula ( p q ) p . ( p q ) p (iii, , omitting outer parens) Construction tree: ( p q ) (iii,) p (i) q (i) p (ii) p (i) Truth table: p 1 1 0 0 q p q p ( p q ) p 1 1 0 1 0 0 0 0 1 1 1 1 0 1 1 1 Boolean operators The connectives , , are called Boolean operators (after George Boole). Those operators have nice formal properties (to be discussed next week) and have been fundamental in the development of modern digital electronics. Boolean operators and searches: https://www.youtube.com/watch?v=lPEmrzTOWEg Special formulas: contingencies Most formulas of propositional logic are true or false, depending on the truth values assigned to their atomic sentences. Such formulas are called contingencies. Contingencies have both 1s and 0s in the final column of their truth table. For example, p q is a contingency: p 1 1 0 0 q 1 0 1 0 pq 1 0 0 0 Fact 1: If is a contingency, is also a contingency. Why? Special formulas: tautologies Some formulas however are always true, independently of the truth values of their atomic sentences. Such formulas are called tautologies. Tautologies only have 1s in the final column of their truth table. For example, p p is a tautology (because p is either true or false, no third option left). p 1 0 p p p 0 1 1 1 Special formulas: contradictions Finally, some formulas are always false, no matter what the truth values of their atomic sentences are. Such formulas are called contradictions. Contradictions only have 0s in the final column of their truth table. For example, p p is a contradiction (because p cannot be both true and false). p 1 0 p p p 0 0 1 0 Fact 2: If is a tautology, is a contradiction (and vice versa). Can you tell why? For next time No new reading!