Mathematical Logic

Statements and notations:

A proposition or statement is a declarative sentence that is either true or false (but not
both). For instance, the following are propositions: “Paris is in France” (true), “London is in
Denmark” (false), “2 < 4” (true), “4 = 7 (false)”. However the following are not propositions:
“what is your name?” (this is a question), “do your homework” (this is a command), “this
sentence is false” (neither true nor false), “x is an even number” (it depends on what x
represents), “Socrates” (it is not even a sentence). The truth or falsehood of a proposition is
called its truth value.
Connectives:
Connectives are used for making compound propositions. The main ones are the
following (p and q represent given propositions):

Name Represente Meani

Negation ¬ “not
Conjunction p∧ “p and
Disjunction pq∨ “p orq q q(or
q qboth)”
Exclusive Or p q⊕ “either p or q, but not
Implication p q→ q both” “if p then q”
Biconditiona p↔q “p if and only if q”
l

Truth Tables:
Logical identity

Logical identity is an operation on one logical value, typically the value of a proposition that
produces a value of true if its operand is true and a value of false if its operand is false

The truth table for the logical identity operator is as follows:

Logical Identity

1
 P P

T T

F F

Logical negation:

Logical negation is an operation on one logical value, typically the value of a proposition that
produces a value of true if its operand is false and a value of false if its operand is true.

The truth table for NOT p (also written as ¬p or ~p) is as follows:

Logical Negation

P ¬p

T F

F T

Binary operations:

Truth table for all binary logical operators:

Here is a truth table giving definitions of all 16 of the possible truth functions of 2 binary
variables (P,Q are thus boolean variables):

P Q 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

T T F F F F F F F F T T T T T T T T

2
 T F F F F F T T T T F F F F T T T T

F T F F T T F F T T F F T T F F T T

F F F T F T F T F T F T F T F T F T

where T = true and F = false.

Key:

0, false, Contradiction

1, NOR, Logical NOR

2, Converse nonimplication

3, ¬p, Negation

4, Material nonimplication

5, ¬q, Negation

6, XOR, Exclusive disjunction

7, NAND, Logical NAND

8, AND, Logical conjunction

9, XNOR, If and only if, Logical biconditional

10, q, Projection function

11, if/then, Logical implication

12, p, Projection function

13, then/if, Converse implication

14, OR, Logical disjunction

15, true, Tautology

Logical operators can also be visualized using Venn diagrams.

Logical conjunction:

Logical conjunction is an operation on two logical values, typically the values of two
propositions, that produces a value of true if both of its operands are true.

The truth table for p AND q (also written as p ∧ q, p & q, or p q) is as follows:

3
 Logical Conjunction

P q p∧q

T T T

T F F

F T F

F F F

In ordinary language terms, if both p and q are true, then the conjunction p ∧ q is true. For all
other assignments of logical values to p and to q the conjunction p ∧ q is false.

It can also be said that if p, then p ∧ q is q, otherwise p ∧ q is p.

Logical disjunction:

Logical disjunction is an operation on two logical values, typically the values of two
propositions, that produces a value of true if at least one of its operands is true.

The truth table for p OR q (also written as p ∨ q, p || q, or p + q) is as follows:

Logical Disjunction

P q p∨q

T T T

T F T

F T T

F F F

4
Logical implication:

Logical implication and the material conditional are both associated with an operation
on two logical values, typically the values of two propositions, that produces a value of false
just in the singular case the first operand is true and the second operand is false.The truth
table associated with the material conditional if p then q (symbolized as p → q) and the
logical implication p implies q (symbolized as p ⇒ q) is as follows:

Logical Implication

P q p→q

T T T

T F F

F T T

F F T

Logical equality:

Logical equality (also known as biconditional) is an operation on two logical values,

typically the values of two propositions, that produces a value of true if both operands are
false or both operands are true.The truth table for p XNOR q (also written as p ↔ q ,p = q,
or p ≡ q) is as follows:

Logical Equality

P q p≡q

T T T

T F F

F T F

5
 F F T

Exclusive disjunction:

Exclusive disjunction is an operation on two logical values, typically the values of

truth table for p XOR q (also written as p ⊕ q, or p ≠ q) is as follows:

two propositions, that produces a value of true if one but not both of its operands is true.The

Exclusive Disjunction

P q p⊕q

T T F

T F T

F T T

F F F

Logical NAND:

The logical NAND is an operation on two logical values, typically the values of two
propositions, that produces a value of false if both of its operands are true. In other words, it
produces a value of true if at least one of its operands is false.The truth table for p NAND q
(also written as p ↑ q or p | q) is as follows:

Logical NAND

P q p↑q

T T F

T F T

6
 F T T

F F T

It is frequently useful to express a logical operation as a compound operation, that is,

as an operation that is built up or composed from other operations. Many such compositions
are possible, depending on the operations that are taken as basic or "primitive" and the
operations that are taken as composite or "derivative".In the case of logical NAND, it is
clearly expressible as a compound of NOT and AND.The negation of a conjunction:
¬(p ∧ q), and the disjunction of negations: (¬p) ∨ (¬q) can be tabulated as follows:

p Q p∧q ¬(p ∧ q) ¬p ¬q (¬p) ∨ (¬q

)

T T T F F F F

T F F T F T T

F T F T T F T

F F F T T T T

Logical NOR:

The logical NOR is an operation on two logical values, typically the values of two
propositions, that produces a value of true if both of its operands are false. In other words, it
produces a value of false if at least one of its operands is true. ↓ is also known as the Peirce
arrow after its inventor, Charles Sanders Peirce, and is a Sole sufficient operator.

The truth table for p NOR q (also written as p ↓ q or p ⊥ q) is as follows:

Logical NOR

P q p↓q

T T F

7
 T F F

F T F

F F T

The negation of a disjunction ¬(p ∨ q), and the conjunction of negations (¬p) ∧ (¬q) can be
tabulated as follows:

p q p∨q ¬(p ∨ q) ¬p ¬q (¬p) ∧ (¬q

)

T T T F F F F

T F T F F T F

F T T F T F F

F F F T T T T

Inspection of the tabular derivations for NAND and NOR, under each assignment of
logical values to the functional arguments p and q, produces the identical patterns of
functional values for ¬(p ∧ q) as for (¬p) ∨ (¬q), and for ¬(p ∨ q) as for (¬p) ∧ (¬q). Thus
the first and second expressions in each pair are logically equivalent, and may be substituted
for each other in all contexts that pertain solely to their logical values.This equivalence is one
of De Morgan's laws.

The truth value of a compound proposition depends only on the value of its
components. Writing F for “false” and T for “true”, we can summarize the meaning of the
connectives in the following way:

p q ¬p p∧q p∨q p⊕q p→q p↔q

T T F T T F T T

8
 T F F F T T F F

F T T F T T T F

F F T F F F T T

Note that ∨ represents a non-exclusive or, i.e., p ∨ q is true when any ofp, q is true and
also when both are true. On the other hand ⊕ represents an exclusive or, i.e., p ⊕ q is true
only when exactly one of p and q is true.

Tautology, Contradiction, Contingency:

A proposition is said to be a tautology if its truth value is T for any assignment of truth values
to its components. Example: The proposition p ∨ ¬p is a tautology.
A proposition is said to be a contradiction if its truth value is F for any assignment of truth
values to its components. Example: The proposition p ∧ ¬p is a contradiction.
A proposition that is neither a tautology nor a contradiction is called a contingency.
P ¬p p ∨ ¬p p ∧ ¬p

T F T F
T F T F
F T T F
F T T F

Equivalence Implication:
We say that the statements r and s are logically equivalent if their truth tables are identical.
For example the truth table of

P q ¬p ∨ p
T T T
T F F
F T T
F F T

shows that is equivalent to . It is easily shown that the statements r and s are
equivalent if and only if is a tautology.

Normal forms:

9
 Let A(P1, P2, P3, …, Pn) be a statement formula where P1, P2, P3, …, Pn are the
atomic variables. If A has truth value T for all possible assignments of the truth values to the
variables P1, P2, P3, …, Pn , then A is said to be a tautology. If A has truth value F, then A is
said to be identically false or a contradiction.
Disjunctive Normal Forms
A product of the variables and their negations in a formula is called an elementary product. A
sum of the variables and their negations is called an elementary sum. That is, a sum of
elementary products is called a disjunctive normal form of the given formula.
Example:

(1)

(2)

(3)

(4)

(5)

Conjunctive Normal Forms

A formula which is equivalent to a given formula and which consists of a product of elementary sums
is called a conjunctive normal form of a given formula.

Example:

(1)

(2)

(3)

(4)

Rules of inference:
The two rules of inference are called rules P and T.
Rule P: A premise may be introduced at any point in the derivation

Rule T: A formula S may be introduced in a derivation if s is tautologically implied by

any one or more of the preceding formulas in the derivation.

Before proceeding the actual process of derivation, some important list of implications and
equivalences are given in the following tables.

10
Implications:
P∧Q ⇒Q
I1 } Simplification
P∧Q ⇒ P
I2 } Simplification
P ⇒ P∨Q
I3 } Addition
Q ⇒ P∨Q
I4 } Addition
¬P ⇒ P →Q
I5
Q ⇒ P→Q
I6
¬( P→Q) ⇒ P
I7
¬( P→Q) ⇒¬Q
I8
P,Q ⇒ P∧Q
I9
¬P,P∨Q⇒ Q
I10 ( disjunctive syllogism)
P,P∨Q⇒ Q
I11 ( modus ponens )
¬Q,P∨Q⇒ ¬P
I12 (modus tollens )
P→Q, Q →R ⇒ P→R
I13 ( hypothetical syllogism)
P∨Q, P→R,Q → R ⇒ R
I14 (dilemma)
Equivalences:

E1 ¬¬P ⇔ P

E2 P∧Q ⇔Q∧P } Commutative laws

E3 P∨Q ⇔Q∨P } Commutative laws

E4 ( P∨Q )∨R ⇔ P∨(Q∨R ) } Associative laws

E5 ( P∧Q )∧R ⇔ P∧(Q∧R ) } Associative laws

11
 E6 P∧(Q∨R )⇔( P∧Q )∨( P∧R) } Distributive laws

E7 P∨(Q∧R )⇔( P∨Q )∧( P∨R) } Distributive laws

¬( P∧Q )⇔¬P∨¬Q
E8

E9 ¬( P∨Q )⇔¬P∧¬Q } De Morgan’s laws

E10 P∨P ⇔ P
E11 P∧P ⇔ P

E12 R∨( P∧¬ P)⇔ R

E13 R∧( P∨¬ P)⇔ R
E14 R∨( P∧¬ P)⇔T
E15 R∧( P∧¬P)⇔ F

E16 P→Q⇔ ¬P∨Q

E17 ¬( P→Q)⇔( P∧¬Q )
E18 P→Q⇔ ¬Q→¬P
E19 P→( Q→ R )⇔( P∧Q )→R
→ →
E20 ¬(P ← Q)⇔¬(P ← ¬Q )
→
E21 (P ← Q)⇔(P →Q)∧(Q→ P)
→
E22 (P ← Q)⇔(P ∧Q )∨(¬Q∧¬P)
Example 1.Show that R is logically derived from P → Q, Q → R, and P
Solution. {1} (1) P→Q Rule P
{2} (2) P Rule P
{1, 2} (3) Q Rule (1), (2) and I11
{4} (4) Q→R Rule P
{1, 2, 4} (5) R Rule (3), (4) and I11.

Example 2.Show that S V R tautologically implied by ( P V Q) ٨ ( P → R) ٨ ( Q → S ).

Solution . {1} (1) PVQ Rule P

{1} (2) 7P → Q T, (1), E1 and E16
{3} (3) Q→S P
{1, 3} (4) 7P → S T, (2), (3), and I13
{1, 3} (5) 7S → P T, (4), E13 and E1

12
 {6} (6) P→R P
{1, 3, 6} (7) 7S → R T, (5), (6), and I13
{1, 3, 6) (8) SVR T, (7), E16 and E1

Example 3. Show that 7Q, P→ Q => 7P

Solution : {1} (1) P→Q Rule P

{1} (2) 7P → 7Q T, and E 18
{3} (3) 7Q P
{1, 3} (4) 7P T, (2), (3), and I11 .

Example 4 .Prove that R ٨ ( P V Q ) is a valid conclusion from the premises PVQ ,

Q → R, P → M and 7M.

Solution . {1} (1) P→M P

{2} (2) 7M P
{1, 2} (3) 7P T, (1), (2), and I12
{4} (4) PVQ P
{1, 2 , 4} (5) Q T, (3), (4), and I10.
{6} (6) Q→R P
{1, 2, 4, 6} (7) R T, (5), (6) and I11
{1, 2, 4, 6} (8) R ٨ (PVQ) T, (4), (7), and I9.

There is a third inference rule, known as rule CP or rule of conditional proof.

Rule CP: If we can derives s from R and a set of premises , then we can derive R → S from
the set of premises alone.

Note. 1. Rule CP follows from the equivalence E10 which states that
( P ٨ R ) → S óP → (R → S).
2. Let P denote the conjunction of the set of premises and let R be any formula
The above equivalence states that if R is included as an additional premise and
S is derived from P ٨ R then R → S can be derived from the premises P alone.
3. Rule CP is also called the deduction theorem and is generally used if the
conclusion is of the form R → S. In such cases, R is taken as an additional
premise and S is derived from the given premises and R.

13
Example 5 .Show that R → S can be derived from the premises
P → (Q → S), 7R V P , and Q.

Solution. {1} (1) 7R V P P

{2} (2) R P, assumed premise
{1, 2} (3) P T, (1), (2), and I10
{4} (4) P → (Q → S) P
{1, 2, 4} (5) Q → S T, (3), (4), and I11
{6} (6) Q P
{1, 2, 4, 6} (7) S T, (5), (6), and I11
{1, 4, 6} (8) R → S CP.

Example 6.Show that P → S can be derived from the premises, 7P V Q, 7Q V R,

and R → S .

Solution:
{1} (1) 7P V Q P
{2} (2) P P, assumed premise
{1, 2} (3) Q T, (1), (2) and I11
{4} (4) 7Q V R P
{1, 2, 4} (5) R T, (3), (4) and I11
{6} (6) R→S P
{1, 2, 4, 6} (7) S T, (5), (6) and I11
{2, 7} (8) P→S CP

Example 7. ” If there was a ball game , then traveling was difficult. If they arrived on time,
then traveling was not difficult. They arrived on time. Therefore, there was no ball game”.
Show that these statements constitute a valid argument.

Solution. Let P: There was a ball game

Q: Traveling was difficult.
R: They arrived on time.

Given premises are: P → Q, R → 7Q and R conclusion is: 7P

14
 {1} (1) P → Q P
{2} (2) R → 7Q P
{3} (3) R P
{2, 3} (4) 7Q T, (2), (3), and I11
{1, 2, 3} (5) 7P T, (2), (4) and I12

Consistency of premises:
Consistency
A set of formulas H1, H2, …, Hm is said to be consistent if their conjunction has the
truth value T for some assignment of the truth values to be atomic appearing in H1, H2, …,
Hm.

Inconsistency

1. If for every assignment of the truth values to the atomic variables, at least one of the
formulas H1, H2, … Hm is false, so that their conjunction is identically false, then the
formulas H1, H2, …, Hm are called inconsistent.
2. A set of formulas H1, H2, …, Hm is inconsistent, if their conjunction implies a
contradiction, that is H1٨ H2٨ … ٨ Hm => R ٨ 7R
3. Where R is any formula. Note that R ٨ 7R is a contradiction and it is necessary and
sufficient that H1, H2, …,Hm are inconsistent the formula.
Indirect method of proof
In order to show that a conclusion C follows logically from the premises H1, H2,…,
Hm, we assume that C is false and consider 7C as an additional premise. If the new set of
premises is inconsistent, so that they imply a contradiction, then the assumption that 7C is
true does not hold simultaneously with H1٨ H2٨ ..… ٨ Hm being true. Therefore, C is
true whenever H1٨ H2٨ ..… ٨ Hm is true. Thus, C follows logically from the premises
H1, H2 ….., Hm.

Example 8: Show that 7(P ٨ Q) follows from 7P٨ 7Q.

Solution.

We introduce 77 (P٨ Q) as an additional premise and show that this additional

premise leads to a contradiction.

15
 {1} (1) 77(P٨ Q) P assumed premise
{1} (2) P٨ Q T, (1) and E1
{1} (3) P T, (2) and I1
{1} {4) 7P٨7Q P
{4} (5) 7P T, (4) and I1
{1, 4} (6) P٨ 7P T, (3), (5) and I9
Here (6) P٨ 7P is a contradiction. Thus {1, 4} viz. 77(P٨ Q) and 7P٨ 7Q leads
to a contradiction P ٨ 7P.
Example 9: Show that the following premises are inconsistent.
1. If Jack misses many classes through illness, then he fails high school.
2. If Jack fails high school, then he is uneducated.
3. If Jack reads a lot of books, then he is not uneducated.
4. Jack misses many classes through illness and reads a lot of books.

Solution.
P: Jack misses many classes.
Q: Jack fails high school.
R: Jack reads a lot of books.
S: Jack is uneducated.
The premises are P→ Q, Q → S, R→ 7S and P٨ R
{1} (1) P→Q P
{2} (2) Q→ S P
{1, 2} (3) P→S T, (1), (2) and I13
{4} (4) R→ 7S P
{4} (5) S → 7R T, (4), and E18
{1, 2, 4} (6) P→7R T, (3), (5) and I13
{1, 2, 4} (7) 7PV7R T, (6) and E16
{1, 2, 4} (8) 7(P٨R) T, (7) and E8
{9} (9) P٨ R P
{1, 2, 4, 9) (10) (P٨ R) ٨ 7(P٨ R) T, (8), (9) and I9

16