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 truthfunctional logic. For now, we will focus on three connectives:

and, or, not; these are called the Boolean connectives. Truth-Table for Negation P P T F F T Truth-Table for Conjunction P T T F F

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

Q PQ T T F T T 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 ) 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: (PQ) (PQ) P T T F F Q T F T F (P Q) (PQ) T F F T

T T T F T T T F F F T 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 T T F

F Q PQ T T F F T T F T If then S) is a conjunction tatements The conditional is used to capture if then statements. However, the match isnt perfect. For example, we dont 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 ifthen expressions arent meant to make a claim that is truth-functional in nature. S) is a conjunction till, 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. S) is a conjunction o, 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 T T F F Q PQ T T F F T F F

T 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 P

T TT F T F F T TF Contradictions A contradiction is a statement that is necessarily false. Example: P P P P P T TF F T F F F TF Contingencies A contingency is a statement that can be true as well as false Example: P

P P T T F F Equivalences Two statements are equivalent if they have the exact same truth-conditions. Example: P and P P P P T T TF T F F F TF 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 T FT F F TF 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 T T F F

Q T F T F P T T F F PQ T T T 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 T T F F Q T F T F

P T T F F P Q Q T F T T T 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 {PQ, Q} P T T F F Q T F T F

P Q Q T F T T T F F T P T T F F

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 T T F F Q T F T F

P Q Q T F T T T F F T P T T F F

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 S) is a conjunction tatements Logically Equivalent S) is a conjunction tatements To express that two statements P and Q are logically equivalent, we will write: PQ 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. S) is a conjunction ome Important Equivalences Double Negation: PP

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: PQQP PQQP Association: P (Q R) (P Q) R P (Q R) (P Q) R Idempotence: PPP PPP S) is a conjunction ubsumption: 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)

S) is a conjunction implifying S) is a conjunction tatements 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 S) is a conjunction ubsumption), we can often simplify statements. Example: (A B) A (Commutation)) (B A) A (Association)) B (A A) (Idempoten)ce) BA Generalized Conjunctions and Generalized Disjunctions Recall the Association equivalences: P (Q R) (P Q) R

P (Q R) (P Q) R Because of this, well allow to drop brackets: PQR PQR Thus we can generalize conjunctions and disjunctions A generalized conjunction (disjunction) can have any number of conjuncts (disjuncts) S) is a conjunction implifying S) is a conjunction tatements 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. S) is a conjunction o, 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 . S) is a conjunction ome equivalences involving and P

P PP PP P P P P S) is a conjunction implifying S) is a conjunction tatements 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 S) is a conjunction entences 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: (AB) (CD) (Distribution)) [(AB)C] [(AB)D] (Distribution) (2x)) (AC) (BC) (AD) (BD) 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:

(AB) (CD) (Distribution)) [(AB) C] [(AB) D] (Distribution) (2x)) (AC) (BC) (AD) (BD) Truth-Functional Connectives S) is a conjunction o 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. S) is a conjunction econd, 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 T T T/F T F T/F F T T/F F F T/F

In) gen)eral: n) sen)ten)ces 2n) truth value combin)ation)s (i.)e.) 2n) rows in) truth table) 2n) 2 differen)t n)-ary con)n)ectives! 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 T T F Step 1: T F T PQ F T

T PQ F F F Step 2: (PQ) (PQ) Truth-Functional Expressive Completeness S) is a conjunction ince I can express any truth 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 T

F F Q P NAND Q T F F T T T F T 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 Logical Possibility All logically interesting claims can be reduced to

questions about logical possibility: Logical Consistency: Is it possible for all statements to be true? Logical Validity: Is it possible for all premises to be true and the conclusion false? Logical Consequence: Is it possible for the implying statements to be true and the implied statement to be false? Logical Equivalence: Is it possible for the two statements to have a different truth value? Logical Tautology: Is it possible for the statement to be false? Truth Table Method The truth table method systematically exhausts all possible truth value combinations of the statements involved.

In the truth-table we look for a row that reflects a certain possibility, and that will tell us the answer to whatever question we had (e.g. if there is no row where statement is false, then it is not possible for that statement to be false, and hence it is a tautology). Drawback and Room for S) is a conjunction olution A drawback of the truth table method is that the number of rows grows exponentially. Fortunately, there is room for a solution to this problem. S) is a conjunction ince all we are interested in, is the existence of a specific combination of truth values of the statements involved, all we need to find is one example of such a case. Once we have found such a case, there is no need to

exhaust all other cases. S) is a conjunction imple S) is a conjunction olution: S) is a conjunction topping Early One solution to the problem of big truth tables is therefore to simply stop once you have found a row that represents the combination of truth values you are interested in. Thus, rather than working out a truth table column by column, you may want to do it row by row, so that you can stop as soon as you have found a row of the kind you are looking for. A big drawback of this approach is that if no row of the kind you are looking for exists, then you have to complete the whole truth table after all. A More Focused S) is a conjunction earch Consider the following argument:

P (Q R)) R) Q R) We are interested in whether all premises can be true and the conclusion false: In order for the conclusion to be false, R must be false. In order for the second premise to be true while R is false, Q must be false. In order for the first premise to be true while Q and R are both false, P must be false. The S) is a conjunction hort Truth Table Method The S) is a conjunction hort Truth Table Method assigns truth values to the involved atomic and complex statements in order to try and obtain a certain combination of truth values:

P (Q R)) F T F FF R) Q F TTF / R) F The S) is a conjunction hort Truth Table Method thus tries to generate one row of the truth table that has the combination of truth values you are interested in. S) is a conjunction hort Truth Table Method and

Indirect Proof As you assign truth values to certain statements, the truth values of other statements can be forced. If you are forced to make a statement both true and false, then you know that the combination of truth values you are looking for does not exist: P (Q P) TF TF F Con)tradiction), so the statemen)t is a tautology! The short truth table method is therefore a kind of indirect proof (proof by contradiction), except that you dont always get a contradiction.

Drawback of the S) is a conjunction hort Truth Table Method A drawback of the short truth table method is that you are not always forced to assign any further truth values: R) (Q P) T T (Q R)) P T T R) P T Q T

At this point, you can choose to assign certain truth values, but if your choice does not lead to the row you are looking for, then you need to try a different option, and the short truth table method has no tools to do go through all of your options in a systematic Truth Trees The obvious solution to the drawback of the short truth table method is to incorporate tools to systematically keep track of multiple options. One method that does so is the truth tree method: The truth tree method tests for the consistency of a set of statements and, as such, can be used to determine validity, tautologies, equivalence, etc.

Like the short table method, it infers which other statements are forced to be true under this assumption. When nothing is forced, then the tree branches into the possible options. Truth Tree Example (((PQ)R)) (P(QR)))) (PQ)R) (P(QR))) P (QR)) Q R) (PQ) R) P Q

((PQ)R)) P(QR)) PQ All bran)ches close R) the origin)al P statemen)t can)n)ot be Q false tautology! P

Q R) Q R) Decomposition Rules for Truth Trees PQ P Q P P

PQ P Q PQ P PQ (PQ) P Q Q P

Q P Q (PQ) P Q (PQ) P Q (PQ) P Q

P Q Truth Trees as Decision Procedures The truth tree method can easily be made into a systematic procedure. As such, the truth tree method becomes a decision procedure for truth-functional consequence that is, on average, quite a bit more efficient than the truth-table method.