Propositional Logic: Connectives, Truth Tables, and Complex Claims

Propositional Logic Review Computability and Logic

Boolean Connectives

Truth-Functional Connectives and Boolean Connectives Connectives are usually called truth-functional connectives: This is because the truth value of a complex claim that has been constructed using a truth-functional connective is considered to be a function of the truth values of the claims that are being connected by that connective. This is also why propositional logic is also called truth-functional logic. For now, we will focus on three connectives: and, or, not; these are called the Boolean connectives.

Truth-Table for Negation P F P T F T

Truth-Table for Conjunction P Q T F P T Q T F T F T F F F F

Truth-Table for Disjunction P Q T T P T Q T F T F T F T F F

Combining Complex Claims: Parentheses Using the truth-functional connectives, we can combine complex claims to make even more complex claims. We are going to use parentheses to indicate the exact order in which claims are being combined. Example: (P Q) (R S) is a conjunction of two disjunctions.

Parentheses and Ambiguity An ambiguous statements is a statement whose meaning is not clear due to its syntax. Example : P or Q and R In formal systems, an expression like P Q R is simply not allowed and considered unsyntactical. Claims in our formal language are therefore never ambiguous. One important application of the use of formal languages is exactly this: to avoid ambiguities!

Exclusive Disjunction vs Inclusive Disjunction Notice that the disjunction as defined by is considered to be true if both disjuncts are true. This is called an inclusive disjunction. However, when I say a natural number is either even or odd , I mean to make a claim that would be considered false if a number turned out to be both even and odd. Thus, I am trying to express an exclusive disjunction.

How to express Exclusive Disjunctions We could define a separate symbol for exclusive disjunctions, but we are not going to do that. Fortunately, exclusive disjunctions can be expressed using the symbols we already have: (P Q) (P Q) (P Q) (P Q) T T T F P T Q T F F T F T T F T F T F T F T T F F F !

Conditionals

The Material Conditional Let us define the binary truth-functional connective according to the truth-table below. The expression P Q is called a conditional. In here, P is the antecedent, and Q the consequent. P Q T F P T Q T F T F T F T T F

If then Statements The conditional is used to capture if then statements. However, the match isn t perfect. For example, we don t want to say that the claim If grass is green then elephants are big is true just because grass is green and elephants are big, nor that any if then statement is automatically true once the if part is false or the then part true. The problem is that most English if then expressions aren t meant to make a claim that is truth-functional in nature. Still, any if then statement will be false if the if part is true, but the then part false, and the conditional captures at least this important truth-functional aspect of any if then statement. So, while we will from now on refer to the conditional as an if then statement, we must be careful about the use of this, just as care must be taken when applying Newtonian physics to some situation.

Case in point: The Infamous King-Ace problem The psychologist of reasoning gave the following logic problem to Princeton undergraduates: Consider the following statement: If there is a king in the hand, then there is an ace in the hand, or else if there is not a king in the hand, then there is an ace in the hand . What follows from this statement? Almost all students responded that it can be inferred that there is an ace in the hand. Johnson-Laird, however, said that what can be concluded is that there is not an ace in the hand, and that this is evidence that people can easily make logical reasoning mistakes! . Really?

If and only if and the Material Biconditional A statement of the form P if and only if Q (or P iff Q ) is short for P if Q, and P only if Q . Hence, we could translate this as (P Q) (Q P). However, since this is a common expression, we define a new connective : P Q T F P T Q T F T F T F F T F

Logical Properties

Truth Tables Truth-tables can be used for: defining the truth-conditions of truth-functional connectives evaluating the truth-conditions of any complex statement

Tautologies A tautology is a statement that is necessarily true. Example: P P P P T T T F P T F T F T F

Contradictions A contradiction is a statement that is necessarily false. Example: P P P P F F T F P T F T F T F

Contingencies A contingency is a statement that can be true as well as false Example: P P P T F T F

Equivalences Two statements are equivalent if they have the exact same truth-conditions. Example: P and P P T F P P T F T F F T T F

Contradictories Two statements are contradictories if one of them is false whenever the other one is true and vice versa. Example: P and P P P P T F T F F T T F

Implication One statement implies a second statement if it is impossible for the second statement to be false whenever the first statement is true. Example: P implies P Q P Q T P T Q P T F T T T T F T F F F T F F

Consistency A set of statements is consistent if it is possible for all of them to be true at the same time. Example: {P, P Q, Q} P Q T Q F P T Q P T F T T T T T F T F F F T F F F T

Consequence A statement is a consequence of a set of statements if it is impossible for the statement to be false while each statement in the set of statements is true. Example: P is a consequence of {P Q, Q} P Q T Q F P T Q P T F T T T T T F T F T F F F F F T

Validity An argument is valid if it is impossible for the conclusion to be false whenever all of its premises are true. Example: P Q, Q P P Q T Q F P T Q P T F T T T T T F T F T F F F F F T

Implication, Consequence, Validity The notions of implication, consequence, and validity are very closely related: A statement implies a statement if and only if is a consequence of the set of statements { } For implication and consequence we use the symbol : If statement implies statement we write If statement is a consequence of a set of statements { 1, , n}, we write { 1, , n} An argument consisting of premises 1, , n and conclusion is valid iff { 1, , n} The terms implication, consequence and validity can therefore be used interchangeably.

Boolean Algebra: Rewriting Statements

Logically Equivalent Statements To express that two statements P and Q are logically equivalent, we will write: P Q is not a symbol of (the language of) propositional logic!! Rather, it is a symbol used to say something about (statements expressed in the language of) propositional logic. It is a meta-logical symbol, expressing a meta-logical claim.

Some Important Equivalences Double Negation: P P DeMorgan: (P Q) P Q (P Q) P Q Distribution: P (Q R) (P Q) (P R) P (Q R) (P Q) (P R) (Q R) P (Q P) (R P) (Q R) P (Q P) (R P)

More Equivalences Commutation: P Q Q P P Q Q P Association: P (Q R) (P Q) R P (Q R) (P Q) R Idempotence: P P P P P P Subsumption: P (P Q) P P (P Q) P

Even More Equivalences Implication: P Q P Q (P Q) P Q Transposition: P Q Q P Exportation: P (Q R) (P Q) R Absorption: P Q P (P Q) Equivalence: P Q (P Q) (Q P) P Q (P Q) ( P Q)

Simplifying Statements I Using the principle of substitution of logical equivalents, and using the logical equivalences that we saw before (Double Negation, Association, Commutation, Idempotence, DeMorgan, Distribution, and Subsumption), we can often simplify statements. Example: (A B) A (Commutation) (B A) A (Association) B (A A) (Idempotence) B A

Generalized Conjunctions and Generalized Disjunctions Recall the Association equivalences: P (Q R) (P Q) R P (Q R) (P Q) R Because of this, we ll allow to drop brackets: P Q R P Q R Thus we can generalize conjunctions and disjunctions A generalized conjunction (disjunction) can have any number of conjuncts (disjuncts)

Simplifying Statements II The conjuncts (disjuncts) of a generalized conjunction (disjunction) can be switched around in any way you want. This really helps with simplifying statements. Example: C (A (B C)) (Distribution) C (A B) (A C) (Subsumption) C (A B)

and A generalized conjunction is false if it has at least one false conjunct, otherwise it is true. So, a generalized conjunction with 0 conjuncts cannot have a false conjunct, and hence cannot be false. Therefore, it is a tautology! We will write this as . A generalized disjunction is true if it has at least one true disjunct, otherwise it is false. Hence, a generalized disjunction with 0 disjuncts can never be true, and is therefore a contradiction! We will write this as .

Some equivalences involving and P P P P P P P P P P

Simplifying Statements III Using and , we can simplify statements even more. Example: ( A ( B ( A B)) (DeMorgan) A ( B ( A B)) (Double Neg.) A B ( A B) (Distribution) (A B A) (A B B)

Normal Forms and Expressive Completeness

Negation Normal Form Literals: Atomic Sentences or negations thereof. Negation Normal Form: An expression built up with , , and literals. Using repeated DeMorgan and Double Negation, we can transform any truth-functional expression built up with , , and into an expression that is in Negation Normal Form. Example: ((A B) C) (DeMorgan) (A B) C (Double Neg, DeM) ( A B) C

Disjunctive Normal Form Disjunctive Normal Form: A disjunction of conjunctions of literals. Using repeated distribution of over , any statement in Negation Normal Form can be written in Disjunctive Normal Form. Example: (A B) (C D) (Distribution) [(A B) C] [(A B) D] (Distribution (2x)) (A C) (B C) (A D) (B D)

Conjunctive Normal Form Conjunctive Normal Form: A conjunction of disjunctions of literals. Using repeated distribution of over , any statement in Negation Normal Form can be written in Conjunctive Normal Form. Example: (A B) (C D) (Distribution) [(A B) C] [(A B) D] (Distribution (2x)) (A C) (B C) (A D) (B D)

Truth-Functional Connectives So far, we have seen one unary truth-functional connective ( ), and two binary truth-functional connectives ( , ). Later, we will see two more binary connectives ( , ) However, there are many more truth-functional connectives possible: First of all, a connective can take any number of arguments: 3 (ternary), 4, 5, etc. Second, there are unary and binary connectives other than the ones listed above.

Unary Connectives What other unary connectives are there besides ? Thinking about this in terms of truth tables, we see that there are 4 different unary connectives: P *P P *P P *P P *P T F T T T F T F T F F T T F F F

Binary Connectives The truth table below shows that there are 24 = 16 binary connectives: P Q P*Q In general: n sentences T T T/F T F T/F 2n truth value combinations (i.e. 2n rows in truth table) F T T/F F F T/F 22ndifferent n-ary connectives!

Expressing other connectives using and , or , and not We saw that we can express the exclusive disjunction using and , or , and not . Q: Can we express all other connectives as well? A: Yes! We can generalize from this example: P Q P*Q Step 1: Step 2: T T F P Q T F T (P Q) ( P Q) P Q F T T F F F

Truth-Functional Expressive Completeness Since I can express anytruth function using , , and , we say that the set of operators { , , } is (truth-functionally) expressively complete. DeMorgan Laws: (P Q) P Q (P Q) P Q Hence, by the principle of substitution of logical equivalents, since { , , } is expressively complete, the sets { , } and { , } are expressively complete as well!

The NAND Let us define the binary truth-functional connective NAND according to the truth-table below. Obviously, P NAND Q (P Q) (hence the name!) P T Q P NAND Q F T T F T F T F T T F

Expressive Completeness of the NAND The NAND has a very interesting property, in that it can express any truth-functional connective, i.e. {NAND} is expressively complete! Proof: We already know that we can express every truth-functional connective using only and . Furthermore: P NAND P (P P) P (P NAND P) NAND (Q NAND Q) ((P NAND P) (Q NAND Q)) ( P Q) P Q In other words, we can build circuitry using only one kind of logic gate!! Of course, the drawback is that we need many of those gates.

Truth-Trees