Introduction To Symbolic Logic

Mathematical Logic Dr Amber Habib Mathematical Sciences Foundation St. Stephen’s College Delhi 110007

Statements ‘A statement is a sentence which is either true or false, but not both simultaneously.’ Examples.

• Two plus two equals four.

• Two plus two equals five.

• All apples are red. 1

Statements 2

• Two plus two equals four.

• Two plus two equals five.

• All apples are red.

The first sentence is obviously true, the second false. The third is certainly either true or false, although it is not immediately clear which! 2

Truth Value The truth or falsity of a statement is called its truth value, and is denoted by T and F respectively. We will use letters such as ments.

p, q, r, . . . as shorthand for various state-

3

Open Statements Consider the following sentence:

• The number N is an integer.

Whether this sentence is true or false depends on the value of N . It is clear that for any choice of N , the sentence is ‘either true or false, but not both simultaneously.’ Therefore we accept it as a statement. Statements of this type, whose truth value is variable, are called open statements. 4

Open Statements Consider the following sentence:

• The number N is an integer.

Whether this sentence is true or false depends on the value of N . It is clear that for any choice of N , the sentence is ‘either true or false, but not both simultaneously.’ Therefore we accept it as a statement. Statements of this type, whose truth value is variable, are called open statements. 4-a

Open Statements Consider the following sentence:

• The number N is an integer.

Whether this sentence is true or false depends on the value of N . It is clear that for any choice of N , the sentence is ‘either true or false, but not both simultaneously.’ Therefore we accept it as a statement. Statements of this type, whose truth value is variable, are called open statements. 4-b

Open Statements Consider the following sentence:

• The number N is an integer.

Whether this sentence is true or false depends on the value of N . It is clear that for any choice of N , the sentence is ‘either true or false, but not both simultaneously.’ Therefore we accept it as a statement. Statements of this type, whose truth value is variable, are called open statements. 4-c

Compound Statements Statements can be combined in various ways to obtain new statements. For instance, we start with the sentences:

• Two plus two equals four.

• Two plus two equals five.

Out of these, we can create the following:

5

Compound Statements 2

• Conjunction: Two plus two equals four and five.

• Disjunction: Two plus two equals four or five.

• Negation: Two plus two does not equal four.

6

Conjunction If p and q are statements, their conjunction is denoted symbol ∧ corresponds to the word “and”. The statement p ∧ have truth value T .

p ∧ q . The

q has truth value T if and only if both p and q

This is also expressed by the following “Truth Table”:

p q T T T F F F F T

p∧q

7

Conjunction If p and q are statements, their conjunction is denoted symbol ∧ corresponds to the word “and”. The statement p ∧ have truth value T .

p ∧ q . The

q has truth value T if and only if both p and q

This is also expressed by the following “Truth Table”:

p q T T T F F F F T

p∧q

7-a

Conjunction If p and q are statements, their conjunction is denoted symbol ∧ corresponds to the word “and”. The statement p ∧ have truth value T .

p ∧ q . The

q has truth value T if and only if both p and q

This is also expressed by the following “Truth Table”:

p q T T T F F F F T

p∧q

7-b

Conjunction If p and q are statements, their conjunction is denoted symbol ∧ corresponds to the word “and”. The statement p ∧ have truth value T .

p ∧ q . The

q has truth value T if and only if both p and q

This is also expressed by the following “Truth Table”:

p q T T T F F F F T

p∧q T

7-c

Conjunction If p and q are statements, their conjunction is denoted symbol ∧ corresponds to the word “and”. The statement p ∧ have truth value T .

p ∧ q . The

q has truth value T if and only if both p and q

This is also expressed by the following “Truth Table”:

p q T T T F F F F T

p∧q T F F F 7-d

Disjunction If p and q are statements, their disjunction is denoted symbol ∨ corresponds to the word “or”.

p ∨ q . The

The statement p ∨ q has truth value T if and only if at least one of p, q has truth value T . This is expressed by the following Truth Table:

p q T T T F F F F T

p∨q

8

Disjunction If p and q are statements, their disjunction is denoted symbol ∨ corresponds to the word “or”.

p ∨ q . The

The statement p ∨ q has truth value T if and only if at least one of p, q has truth value T . This is expressed by the following Truth Table:

p q T T T F F F F T

p∨q

8-a

Disjunction If p and q are statements, their disjunction is denoted symbol ∨ corresponds to the word “or”.

p ∨ q . The

The statement p ∨ q has truth value T if and only if at least one of p, q has truth value T . This is expressed by the following Truth Table:

p q T T T F F F F T

p∨q

8-b

Disjunction If p and q are statements, their disjunction is denoted symbol ∨ corresponds to the word “or”.

p ∨ q . The

The statement p ∨ q has truth value T if and only if at least one of p, q has truth value T . This is expressed by the following Truth Table:

p q T T T F F F F T

p∨q T

8-c

Disjunction If p and q are statements, their disjunction is denoted symbol ∨ corresponds to the word “or”.

p ∨ q . The

The statement p ∨ q has truth value T if and only if at least one of p, q has truth value T . This is expressed by the following Truth Table:

p q T T T F F F F T

p∨q T T

8-d

Disjunction If p and q are statements, their disjunction is denoted symbol ∨ corresponds to the word “or”.

p ∨ q . The

The statement p ∨ q has truth value T if and only if at least one of p, q has truth value T . This is expressed by the following Truth Table:

p q T T T F F F F T

p∨q T T F T 8-e

Negation If p is a statement, its negation is denoted corresponds to the word “not”. The statement F.

∼ p. The symbol ∼

∼p has truth value T if and only if p has truth value

This is expressed by the following Truth Table:

p T F

∼p

9

Negation If p is a statement, its negation is denoted corresponds to the word “not”. The statement F.

∼ p. The symbol ∼

∼p has truth value T if and only if p has truth value

This is expressed by the following Truth Table:

p T F

∼p F T 9-a

Connectives The symbols

∧, ∨, ∼ are called connectives.

They can be used repeatedly to create statements of any complexity, such as •

p ∧ (q ∧ r)

•

p ∧ (q ∨ r)

•

∼(p ∧ q)

•(∼(p ∧ q)) ∨ (p ∧ (∼r))

Note the use of brackets to clarify the order in which the connectives are to be applied.

10

Conditionals Consider a sentence of the form • If

where

p then q . p and q are statements. It asserts that the truth value of q is

T whenever the truth value of

p is T . Thus the sentence is itself a

statement, and we represent it symbolically by

p→q The symbol

→ is called the conditional. 11

Conditionals 2 The Truth Table of

p → q is p q T T T F F F F T

p→q T F T T

Note that this is the same Truth Table as for

∼p ∨ q .

12

Bi-conditional The conjunction of the statements

p → q and q → p is denoted

p↔q The symbol is

↔ is called the bi-conditional. The Truth Table of p ↔ q

p q T T T F F F F T

p↔q T F T F 13

Statement Forms Logic is concerned with valid forms of arguments rather than with the literal truth or falsity of any particular statement. For instance, the following sequence of statements would be accepted as logically satisfactory: If Socrates is a man, then Socrates is mortal. Socrates is a man. ∴ Socrates is mortal.

p→q p ∴q

But the following is not logically satisfactory: Socrates is a man. if then Socrates is mortal. ∴ Socrates is mortal.

p then q ∴q 14

Statement Forms Logic is concerned with valid forms of arguments rather than with the literal truth or falsity of any particular statement. For instance, the following sequence of statements would be accepted as logically satisfactory: If Socrates is a man, then Socrates is mortal. Socrates is a man. ∴ Socrates is mortal.

p→q p ∴q

But the following is not logically satisfactory: Socrates is a man. then Socrates is mortal. ∴ Socrates is mortal.

p then q ∴q 14-a

Statement Forms 2 In order to emphasize form, we treat the symbols p, q, r,. . . as variables for which any particular statement can be substituted. We then call them statement variables. Statement variables can be combined via the connectives ∧, ∨, ∼ and the conditionals →, ↔ to give more complicated expressions. These are called statement forms.

15

Statement Forms 3

We will denote statement forms by capital letters like S. If we wish to indicate the statement variables involved in S, we will use functional notation. For instance:

S(p, q, r) = p ∨ (q ∧ (∼r))

16

Truth Tables One of the aims of Logic is to analyze how the truth value of a statement form depends on the truth values of the statement variables out of which it is constructed. This information can be displayed via Truth Tables, as we have already illustrated for the statement forms p ∧ q , p ∨ q , and ∼p.

17

Truth Tables 2

Here is a more complicated example:

∼(p ∨ q) p q T T T F F F F T

p ∨ q ∼(p ∨ q)

18

Truth Tables 2

Here is a more complicated example:

∼(p ∨ q) p q T T T F F F F T

p ∨ q ∼(p ∨ q) T T F T 18-a

Truth Tables 2

Here is a more complicated example:

∼(p ∨ q) p q T T T F F F F T

p ∨ q ∼(p ∨ q) T F T F F T T F 18-b

Truth Tables 3 Here is another example:

(∼p) ∧ (∼q) p q T T T F F F F T

∼p ∼q (∼p) ∧ (∼q)

19

Truth Tables 3 Here is another example:

(∼p) ∧ (∼q) p q T T T F F F F T

∼p ∼q (∼p) ∧ (∼q) F F T T 19-a

Truth Tables 3 Here is another example:

(∼p) ∧ (∼q) p q T T T F F F F T

∼p ∼q (∼p) ∧ (∼q) F F F T T T T F 19-b

Truth Tables 3 Here is another example:

(∼p) ∧ (∼q) p q T T T F F F F T

∼p ∼q (∼p) ∧ (∼q) F F F F T F T T T T F F 19-c

Logical Equivalence Two statement forms are logically equivalent (or just equivalent) if they are always both true or both false. This can be decided by looking at their Truth Tables. If R, S are equivalent statement forms, we write R≡S

20

Logical Equivalence 2 Example. Consider the statement form

p T F Therefore

∼(∼p). Its Truth Table is

∼p ∼(∼p) F T T F

p and ∼(∼p) are equivalent: p ≡ ∼(∼p)

21

Logical Equivalence 3 Example. Consider the statement forms ∼(p ∨ q) and (∼p) ∧ (∼q). We have already worked out their Truth Tables, and we combine that information below:

p q T T T F F F F T

∼(p ∨ q) (∼p) ∧ (∼q) F F F F T T F F

Hence the two are equivalent:

∼(p ∨ q) ≡ (∼p) ∧ (∼q) 22

Tautology A statement form is called a tautology if it can take only the value T. Clearly, all tautologies are logically equivalent. Example. Consider the statement form

p T F Hence

p ∨ ∼p. Its Truth Table is

∼p p ∨ ∼p F T T T

p ∨ ∼p is a tautology. 23

Tautology A statement form is called a tautology if it can take only the value T. Clearly, all tautologies are logically equivalent. Example. Consider the statement form

p T F Hence

p ∨ ∼p. Its Truth Table is

∼p p ∨ ∼p F T T T

p ∨ ∼p is a tautology. 23-a

Contradiction A statement form is called a contradiction if it can take only the value F. All contradictions are logically equivalent. Example. Consider the statement form

p T F Hence

p ∧ ∼p. Its Truth Table is

∼p p ∧ ∼p F F T F

p ∧ ∼p is a contradiction. 24

Contradiction A statement form is called a contradiction if it can take only the value F. All contradictions are logically equivalent. Example. Consider the statement form

p T F Hence

p ∧ ∼p. Its Truth Table is

∼p p ∧ ∼p F F T F

p ∧ ∼p is a contradiction. 24-a

Logic and Sets Consider a typical statement: ‘The number N is an integer.’ This has the form: ‘The object X has property A,’ with X being a member of some set (in our example, the set is that of numbers). A statement of this form immediately leads to the creation of a set — consisting of those X which do have the property A. Conversely, every set S creates a statement: ‘X is a member of S.’ Thus there is a correspondence between statements and sets. 25

Logic and Sets 2 Consider a statement p = ‘X has property A’, where X varies over a set U . The corresponding set P consists of those X ∈ U which do have property A.

• If

p is a tautology, then every X has property A, so P = U .

• If

p is a contradiction, then no X has property A, so P = ∅.

26

Logic and Set Theory We just saw a correspondence between the objects of Logic and Set Theory (statements and sets). This correspondence extends to the operations of Logic and Set Theory. Consider two statements: •

p = ‘X has property A’

•

q = ‘X has property B’

where X varies over a set U . Let P, Q be the corresponding sets. 27

Union and Disjunction

With the notation of the previous slide, we have:

p ∨ q = ‘X has property A or B’ The corresponding set is {X ∈ U : X has property A or B} = {X ∈ U : X has property A} ∪ {X ∈ U : X has property B} = P ∪Q Therefore the operation of Set Theory.

∨ of Logic corresponds to the operation ∪ 28

Intersection and Conjunction The set corresponding to p ∧ q is P ∩ Q. Therefore the operation of Logic corresponds to the operation ∩ of Set Theory.

∧

Complement and Negation The set corresponding to ∼ p is P c, the complement of P in U . Therefore the operation ∼ of Logic corresponds to the operation of complement in Set Theory. This correspondence between Logic and Set Theory shows Logic must follow the same algebraic rules as Set Theory. Thus we can guess facts of Logic by starting from facts about Sets. These guesses can be confirmed by Truth Tables. 29

Important Equivalences • Idempotent Law:

p ∨ p ≡ p ∧ p ≡ p.

• Commutative Law:

p ∨ q ≡ q ∨ p,

p ∧ q ≡ q ∧ p.

• Associative Law:

p ∨ (q ∨ r) ≡ (p ∨ q) ∨ r p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r 30

Important Equivalences 2

• Distributive Law:

p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) • De Morgan’s Laws:

∼(p ∧ q) ≡ (∼p) ∨ (∼q) ∼(p ∨ q) ≡ (∼p) ∧ (∼q) 31

Important Equivalences 3 We let

t be a tautology and c a contradiction.

Relative to these, the operations obey:

•

p ∨ c ≡ p,

p ∧ c ≡ c.

•

p ∧ t ≡ p,

p ∨ t ≡ t.

•

p ∨ ∼p ≡ t,

p ∧ ∼p ≡ c. 32

Important Equivalences 3 We let

t be a tautology and c a contradiction.

Relative to these, the operations obey:

•

p ∨ c ≡ p,

p ∧ c ≡ c.

•

p ∧ t ≡ p,

p ∨ t ≡ t.

•

p ∨ ∼p ≡ t,

p ∧ ∼p ≡ c. 32-a

Important Equivalences 3 We let

t be a tautology and c a contradiction.

Relative to these, the operations obey:

•

p ∨ c ≡ p,

p ∧ c ≡ c.

•

p ∧ t ≡ p,

p ∨ t ≡ t.

•

p ∨ ∼p ≡ t,

p ∧ ∼p ≡ c. 32-b

Important Equivalences 3 We let

t be a tautology and c a contradiction.

Relative to these, the operations obey:

•

p ∨ c ≡ p,

p ∧ c ≡ c.

•

p ∧ t ≡ p,

p ∨ t ≡ t.

•

p ∨ ∼p ≡ t,

p ∧ ∼p ≡ c. 32-c

An Application Absorption Law.

p ∧ (p ∨ q) ≡ p ∨ (p ∧ q) ≡ p.

Proof. The Distributive Law gives:

p ∧ (p ∨ q) ≡ (p ∧ p) ∨ (p ∧ q) ≡ p ∨ (p ∧ q) Next:

p ∧ (p ∨ q) ≡ (p ∨ c) ∧ (p ∨ q) ≡ p ∨ (c ∧ q) ≡ p ∨ c ≡ p 33

An Application Absorption Law.

p ∧ (p ∨ q) ≡ p ∨ (p ∧ q) ≡ p.

Proof. The Distributive Law gives:

p ∧ (p ∨ q) ≡ (p ∧ p) ∨ (p ∧ q) ≡ p ∨ (p ∧ q) Next:

p ∧ (p ∨ q) ≡ (p ∨ c) ∧ (p ∨ q) ≡ p ∨ (c ∧ q) ≡ p ∨ c ≡ p 33-a

An Application Absorption Law.

p ∧ (p ∨ q) ≡ p ∨ (p ∧ q) ≡ p.

Proof. The Distributive Law gives:

p ∧ (p ∨ q) ≡ (p ∧ p) ∨ (p ∧ q) ≡ p ∨ (p ∧ q) Next:

p ∧ (p ∨ q) ≡ (p ∨ c) ∧ (p ∨ q) ≡ p ∨ (c ∧ q) ≡ p ∨ c ≡ p 33-b

An Application Absorption Law.

p ∧ (p ∨ q) ≡ p ∨ (p ∧ q) ≡ p.

Proof. The Distributive Law gives:

p ∧ (p ∨ q) ≡ (p ∧ p) ∨ (p ∧ q) ≡ p ∨ (p ∧ q) Next:

p ∧ (p ∨ q) ≡ (p ∨ c) ∧ (p ∨ q) ≡ p ∨ (c ∧ q) ≡ p ∨ c ≡ p 33-c

Notation and Conventions

• Due to the Associative Law, there is no ambiguity in writing

p∧q∧r

or

p∨q∨r

34

Notation and Conventions

• Due to the Associative Law, there is no ambiguity in writing

p∧q∧r

or

p∨q∨r

• When negation is used without brackets, it is to be applied only to the statement immediately succeeding it. Thus,

p ∧ ∼q ∧ r

is read as

p ∧ (∼q) ∧ r 34-a

Implication

Let R, S be statement forms.

We say R logically implies S if the

statement form

R→S is a tautology.

35

Implication 2

Example.

p ∧ q logically implies p since (p ∧ q) → p ≡ ∼(p ∧ q) ∨ p ≡ ∼p ∨ ∼q ∨ p ≡ ∼q ∨ (∼p ∨ p) ≡ ∼q ∨ t ≡ t

36

Argument Forms An Argument Form is an expression of the type S 1 , S 2 . . . , SN ;

∴S

where S1, S2, . . . , SN and S are statement forms. The statement forms S1, S2, . . . , SN are called premises or hypotheses, while S is the conclusion.

37

Valid Arguments An argument form S1, S2 . . . , SN ;

∴ S, is valid if the statement form

(S1 ∧ S2 ∧ · · · ∧ SN ) → S is a tautology. Therefore, an argument is invalid if it is possible to assign truth values to the concerned statement variables such that each premise has truth value T but the conclusion has truth value F .

38

Valid Arguments An argument form S1, S2 . . . , SN ;

∴ S, is valid if the statement form

(S1 ∧ S2 ∧ · · · ∧ SN ) → S is a tautology. Therefore, an argument is invalid if it is possible to assign truth values to the concerned statement variables such that each premise has truth value T but the conclusion has truth value F .

38-a

A Valid Argument Question. Is the following argument form valid?

p → (q → r), q ;

∴ p → r.

Solution 1.

[(p → (q → r)) ∧ q] → [p → r] ≡ ∼[(p → (q → r)) ∧ q] ∨ [p → r] ≡ ∼[(∼p ∨ ∼q ∨ r) ∧ q] ∨ [p → r] 39

A Valid Argument Question. Is the following argument form valid?

p → (q → r), q ;

∴ p → r.

Solution 1. (contd.)

· · · ≡ ∼[(∼p ∨ ∼q ∨ r) ∧ q] ∨ [p → r] ≡ ∼[(∼p ∨ r) ∧ q] ∨ [∼p ∨ r] ≡ (p ∧ ∼r) ∨ ∼q ∨ ∼(p∧ ∼r) ≡ t ∨ ∼q ≡ t, so the argument is valid. 39-a

A Valid Argument 2 Question. Is the following argument form valid?

p → (q → r), q ;

∴ p → r.

Solution 2. Suppose we have assigned truth values to the statement variables such that the premises are true. We have to show the conclusion is also true. Case I: If is true.

p has value F , then p → r has value T , so the conclusion

Case II: If p has value T , then q → r has value T . Since q also has value T , r has value T . Again, the conclusion p → r has value T . 40

A Valid Argument 2 Question. Is the following argument form valid?

p → (q → r), q ;

∴ p → r.

Solution 2. Suppose we have assigned truth values to the statement variables such that the premises are true. We have to show the conclusion is also true. Case I: If is true.

p has value F , then p → r has value T , so the conclusion

Case II: If p has value T , then q → r has value T . Since q also has value T , r has value T . Again, the conclusion p → r has value T . 40-a

A Valid Argument 2 Question. Is the following argument form valid?

p → (q → r), q ;

∴ p → r.

Solution 2. Suppose we have assigned truth values to the statement variables such that the premises are true. We have to show the conclusion is also true. Case I: If is true.

p has value F , then p → r has value T , so the conclusion

Case II: If p has value T , then q → r has value T . Since q also has value T , r has value T . Again, the conclusion p → r has value T . 40-b

An Invalid Argument

Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 1. We ask if we can assign truth values such that the premises are true but the conclusion is false. If the conclusion is false, then p has value F . Then the premise p → q has value T . If we assign value T to r , then the other two premises also have value T (regardless of the value of q ). Therefore this argument form is invalid. 41

An Invalid Argument

Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 1. We ask if we can assign truth values such that the premises are true but the conclusion is false. If the conclusion is false, then p has value F . Then the premise p → q has value T . If we assign value T to r , then the other two premises also have value T (regardless of the value of q ). Therefore this argument form is invalid. 41-a

An Invalid Argument

Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 1. We ask if we can assign truth values such that the premises are true but the conclusion is false. If the conclusion is false, then p has value F . Then the premise p → q has value T . If we assign value T to r , then the other two premises also have value T (regardless of the value of q ). Therefore this argument form is invalid. 41-b

An Invalid Argument Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 2.

[(p → q) ∧ (∼q → r) ∧ r] → p ≡ ∼[(∼p ∨ q) ∧ (q ∨ r) ∧ r] ∨ p ≡ ∼[(∼p ∨ q) ∧ r] ∨ p ≡ (p∧ ∼q)∨ ∼r ∨ p ≡ p∨ ∼r 6≡ t,

so the argument is invalid.

42

An Invalid Argument Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 2.

[(p → q) ∧ (∼q → r) ∧ r] → p ≡ ∼[(∼p ∨ q) ∧ (q ∨ r) ∧ r] ∨ p ≡ ∼[(∼p ∨ q) ∧ r] ∨ p ≡ (p∧ ∼q)∨ ∼r ∨ p ≡ p∨ ∼r 6≡ t,

so the argument is invalid.

42-a

An Invalid Argument Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 2.

[(p → q) ∧ (∼q → r) ∧ r] → p ≡ ∼[(∼p ∨ q) ∧ (q ∨ r) ∧ r] ∨ p ≡ ∼[(∼p ∨ q) ∧ r] ∨ p ≡ (p ∧ ∼q) ∨ ∼r ∨ p ≡ p∨ ∼r 6≡ t,

so the argument is invalid.

42-b

An Invalid Argument Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 2.

[(p → q) ∧ (∼q → r) ∧ r] → p ≡ ∼[(∼p ∨ q) ∧ (q ∨ r) ∧ r] ∨ p ≡ ∼[(∼p ∨ q) ∧ r] ∨ p ≡ (p ∧ ∼q) ∨ ∼r ∨ p ≡ p ∨ ∼r 6≡ t,

so the argument is invalid.

42-c

An Invalid Argument Question. Is the following argument form valid?

p → q, ∼q → r, r ;

∴ p.

Solution 2.

[(p → q) ∧ (∼q → r) ∧ r] → p ≡ ∼[(∼p ∨ q) ∧ (q ∨ r) ∧ r] ∨ p ≡ ∼[(∼p ∨ q) ∧ r] ∨ p ≡ (p ∧ ∼q) ∨ ∼r ∨ p ≡ p ∨ ∼r 6≡ t,

so the argument is invalid.

42-d