### Propositional Logic

A

- The Earth revolves around the Sun;
- \(10 + 3 = 13;\)
- If \(x\) is an even integer, then \({x^2}\) is also even.

Examples of

- An electron is heavier than a proton;
- \(1 + 2 \gt 3;\)
- \(6\) is a prime number.

Not all sentences are propositions:

- \(x \gt 5\) (This may be true or false depending on \(x\))
- Is it raining? (This is a question, not a declarative sentence)
- Mondrian paintings are too abstract. (What is abstract and too abstract?)

To represent propositions, we denote them by letters. The most common letters are \(p,\) \(q,\) \(r,\) \(s,\) \(t.\)

Using

### Logical Operators and Truth Tables

Let \(p\) and \(q\) be two propositions. Each of these statements can take two values – true (\(T\)) and false (\(F\)). So there are \(4\) pairs of input values: \(TT,\) \(TF,\) \(FT,\) and \(FF.\)

Suppose that a new proposition \(r\) is composed of \(p\) and \(q.\) The truth values of the proposition \(r\) can take different values (\(T\) or \(F\)) for each pair of input values.

There are total \(2^4 = 16\) possible output combinations (truth functions) for \(2\) binary input variables. Each of these combinations is represented by a certain logical operator.

Further we’ll look at the most important operators.

#### Negation

Negation is a unary logical operator. If \(p\) is a proposition, then the negation of \(p\) is called not \(p\) and is denoted by \(\lnot p.\)

To represent the meaning of a logical expression, it is convenient to use a truth table. Each row of the table contains one possible configuration of the input variables and truth values of the output proposition(s).

In case of the negation operator, the truth table is very simple:

As you can see, the logical negation operator reverses the truth value of the input proposition.

__Example 1__:

\(p:\) | A trapezoid is a quadrilateral (true) |

\(\lnot p:\) | A trapezoid is not a quadrilateral (false) |

__Example 2__:

\(p:\) | \(2\) is a prime number (true) |

\(\lnot p:\) | \(2\) is not a prime number (false) |

Сonsider now some binary operators.

#### Conjunction

If \(p\) and \(q\) are two propositions, then their conjunction means \(p\) and \(q\) and is denoted by \(p \land q.\)

The conjunction \(p \land q\) is true only when both \(p\) and \(q\) are true. Otherwise, it is false. Thus, the truth table for conjunction looks as follows:

__Example 1__:

\(p:\) | United Kingdom is a member of European Union (false) |

\(q:\) | Ireland is a member of European Union (true) |

\(p \land q:\) | United Kingdom and Ireland are members of European Union (false) |

__Example 2__:

\(p:\) | \(3\) is prime (true) |

\(q:\) | \(3\) is odd (true) |

\(p \land q:\) | \(3\) is prime and odd (true) |

#### Disjunction

If \(p\) and \(q\) are two propositions, then their disjunction means \(p\) or \(q\) and is denoted by \(p \lor q.\)

The disjunction \(p \lor q\) is true when either \(p\) is true, \(q\) is true, or both are true. It is false, if both \(p\) and \(q\) are false.

Truth table for disjunction:

__Example 1__:

\(p:\) | A proton has a negative charge (false) |

\(q:\) | A neutron has a negative charge (false) |

\(p \lor q:\) | A proton or a neutron has a negative charge (false) |

__Example 2__:

\(p:\) | \(\large{\frac{2}{3}}\normalsize\) is a rational number (true) |

\(q:\) | \(\large{\frac{\sqrt{2}}{5}}\normalsize\) is a rational number (false) |

\(p \lor q:\) | Either \(\large{\frac{2}{3}}\normalsize\) or \(\large{\frac{\sqrt{2}}{5}}\normalsize\) or both the numbers are rational (true) |

#### Material Conditional

The material conditional of \(p\) and \(q\) means the statement if \(p\) then \(q\) and is denoted by \(p \to q.\) This logical operator is also called just a conditional statement.

If \(p\) is true, then the conditional \(p \to q\) takes the truth value of \(q.\) If \(p\) is false, then the conditional \(p \to q\) is assumed to be true by default.

Here is the truth table for conditional statement:

The conditional \(p \to q\) can be expressed by different sentences, some of them are listed below:

- \(p\) implies \(q\)
- \(p\) is a sufficient condition for \(q\)
- \(q\) is a necessary condition for \(p\)
- \(q\) follows from \(p\)
- \(p\) only if \(q\)

__Example__:

\(p:\) | \(x\) is divisible by \(2\) and \(3\) |

\(q:\) | \(x\) is divisible by \(6\) |

\(p \to q:\) | If \(x\) is divisible by \(2\) and \(3,\) then \(x\) is divisible by \(6.\) |

\(x = 12:\) | \(p\) is true, \(q\) is true, and \(p \to q\) is true. |

\(x = 13:\) | \(p\) is false, \(q\) is false, and \(p \to q\) is true. |

#### Special Conditional Propositions

- The converse of \(p \to q\) is the proposition \(q \to p\)
- The contrapositive of \(p \to q\) is the proposition \(\neg q \to \neg p\)
- The inverse of \(p \to q\) is the proposition \(\neg p \to \neg q\)

If the statement \(p \to q\) is true, then the contrapositive is also true. If the converse is true, then the inverse is also true.

The special conditional operators are defined by the following truth table:

__Example__:

Statement \(p\) |

A quadrilateral is a rectangle (false) |

Statement \(q\) |

The sum of interior angles of a quadrilateral is \(360\) degrees (true). |

Conditional statement \(p \to q\) |

If a quadrilateral is a rectangle, then the sum of its interior angles is \(360\) degrees (true). |

Converse of \(p \to q:\) \(q \to p\) |

If the sum of interior angles of a quadrilateral is \(360\) degrees, then it is a rectangle (false). |

Inverse of \(p \to q:\) \(\neg p \to \neg q\) |

If a quadrilateral is a not a rectangle, then the sum of its interior angles is not \(360\) degrees (false). |

Contrapositive of \(p \to q:\) \(\neg q \to \neg p\) |

If the sum of interior angles of a quadrilateral is not \(360\) degrees, then it is not a rectangle (true). |

#### Material Biconditional

The material biconditional or logical biconditional of \(p\) and \(q\) means the statement \(p\) if and only if \(q\) and is denoted by \(p \leftrightarrow q.\)

The biconditional statement has the same truth value as the compound logical operator \(\left( {p \to q} \right) \land \left( {q \to p} \right),\) which means \(p\) implies \(q\) and \(q\) implies \(p.\)

The truth table for biconditional statement has the form

__Example 1__:

\(p:\) | Three vectors are coplanar (true) |

\(q:\) | The scalar triple product of three vectors is zero (true) |

\(p \leftrightarrow q:\) | Three vectors are coplanar if and only if their scalar triple product is zero (true) |

__Example 2__:

\(p:\) | The tennis match will be played outdoors (false) |

\(q:\) | It is raining (true) |

\(p \leftrightarrow q:\) | The tennis match will be played outdoors if and only if it is raining (false) |

#### Logical Equivalence

Propositions \(p\) and \(q\) are said to be logically equivalent if they have the same truth tables. The logical equivalence of \(p\) and \(q\) is denoted as \(p \equiv q,\) or sometimes by \(\Leftrightarrow\) depending on the notation being used.

### Predicates and Quantifiers

So far, we considered propositions which are defined as statements that can be either true or false.

To extend the simple propositional logic, we introduce the concept of predicate.

A predicate is a logical statement that contains one or more variables or parameters. The predicates are denoted by a capital letter and the variables listed as arguments, like \(P\left( x \right)\) or \(Q\left( {x,y} \right).\) The truth value of a predicate depends on the values of its variables.

__Example 1__:

Predicate \(P\left( x \right)\) | |

\(P\left( x \right):\) \(x\) is a planet | |

\(x\) = Venus | True proposition |

\(P\left( \text{Venus} \right):\) Venus is a planet | |

\(x\) = Antares | False proposition |

\(P\left( \text{Antares} \right):\) Antares is a planet |

__Example 2__:

Predicate \(Q\left( {x,y} \right)\) | |

\(Q\left( {x,y} \right): {x^2} + {y^2} \le 4\) | |

\(x = 1, y = -1\) | True proposition |

\(Q\left( {1,-1} \right): {1^2} + {\left( { – 1} \right)^2} \le 4\) | |

\(x = 1, y = 2\) | False proposition |

\(Q\left( {1,2} \right): {1^2} + {2^2} \le 4\) |

Similarly to propositions, predicate take two values – true or false. Therefore, all operations of logic algebra are applicable to them. Using the operators \(\neg, \land, \lor, \rightarrow,\) and \(\leftrightarrow,\) we can form more complex predicates.

There is also an additional operation defined on predicates and called quantification. Quantification allows us to specify the extent of validity of a predicate, that is, the range of values of variables for which the predicate should hold.

There are two types of quantifiers in predicate logic − universal quantifier and existential quantifier.

#### Universal Quantifier

The universal quantifier is used to express sentences with words like all or every. It is denoted by the symbol \(\forall.\) The notation \(\forall x P\left({x}\right)\) means “for every value of \(x\) in a particular domain, the predicate \(P\left({x}\right)\) is true”. The domain is called the universe of discourse or domain of discourse.

#### Existential Quantifier

The existential quantifier is used to express sentences with words like some or there is a. It is denoted by the symbol \(\exists.\) The notation \(\exists x P\left({x}\right)\) means “there is some value of \(x\) such that \(P\left({x}\right)\) is true”.

Predicates, logical operators, and quantifiers are a powerful set of tools for describing mathematical objects and for modeling the real world.

### Set Builder Notation

The set builder notation is used to specify a set of objects by means of a predicate. The common notation includes \(3\) parts: a variable \(x,\) a colon or vertical bar separator, and a logical predicate \(P\left({x}\right):\)

\[S = \left\{ {x|P\left( x \right)} \right\},\]

where \(S\) denotes the set of objects.

The single variable \(x\) can be replaced with a term that may include one or more variables, combined with functions acting on them. The predicate \({P\left( x \right)}\) may be represented by a complex logical formula.

#### Some Other Definitions and Notations

\(\{\;\} \) | is a set |

\(x \in S\) | \(x\) is an element or member of \(S\) |

\(x \notin S\) | \(x\) is not an element of \(S\) |

\(S \subseteq T\) | \(S\) is a subset of \(T\) |

\(S = T\) | is equivalent to \(\left({S \subseteq T}\right) \land \left({T \subseteq S}\right)\) |

\(S \subset T\) | \(S\) is a proper subset of \(T.\) This means \(\left({S \subseteq T}\right) \land \left({T \ne S}\right)\) |

\(\require{AMSsymbols}\varnothing\) | the empty set |

## Solved Problems

Click a problem to see the solution.

### Example 1

Prove De Morgan’s Laws: \[\neg \left( {p \land q} \right) \equiv \left( {\neg p} \right) \lor \left( {\neg q} \right),\] \[\neg \left( {p \lor q} \right) \equiv \left( {\neg p} \right) \land \left( {\neg q} \right).\]### Example 2

Show that the statement \[s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\] is a tautology.### Example 3

Show that the statement \[r = (\neg p \land q) \land (p \leftrightarrow q)\] is a contradiction.### Example 4

Prove the distributive law \[p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).\]### Example 5

Let \(G\left( {x,y} \right)\) be the predicate “\(x\) goes to the gym \(y\) times a week.” Write the following propositions in predicate notation:- Nick goes to the gym \(4\) times a week.
- Nicole goes to the gym \(2\) or \(3\) times a week.
- Max goes to the gym 2 times a week, but not every week.
- Amy sometimes goes to the gym.
- Some people go to the gym every day.
- Hardly anyone goes to the gym 15 times a week.

### Example 6

Suppose \(x\) is a student, \(y\) is a math course, and \(M\left( {x,y} \right)\) is the predicate “\(x\) will take \(y\)”. Translate the following sentences into predicate notation:- Every student will take Calculus.
- Every student will take a math course.
- Lora will take Calculus and Linear Algebra.
- There is a course that everybody will take.
- There is a course that nobody will take.
- Tom will take all math courses except Topology.

### Example 7

Describe the following sets using set builder notation:- \(\left\{ { – 27, – 8, – 1,0,1,8,27} \right\}\)
- \(\left\{ {\large{\frac{1}{2}}\normalsize, \large{\frac{2}{3}}\normalsize, \large{\frac{3}{4}}\normalsize, \large{\frac{4}{5}}\normalsize, \large{\frac{5}{6}}\normalsize} \right\}\)
- \(\left\{ {5,8,13,21,34,55} \right\}\)

### Example 1.

Prove De Morgan’s Laws: \[\neg \left( {p \land q} \right) \equiv \left( {\neg p} \right) \lor \left( {\neg q} \right),\] \[\neg \left( {p \lor q} \right) \equiv \left( {\neg p} \right) \land \left( {\neg q} \right).\]Solution.

We verify the \(1\text{st}\) De Morgan’s Law using truth table.

First we write all possible combinations of the propositions \(p\) and \(q.\) The negations of \(p\) and \(q\) are their opposite values. The expression \(p \land q\) is conjunction of \(p\) and \(q.\) Then we determine the negation of conjunction \(\neg \left({p \land q}\right)\). The expression \(\left( {\neg p} \right) \lor \left( {\neg q} \right)\) is disjunction of \(\neg p\) and \(\neg q.\)

We see that the last two columns of the truth table are the same. This proves the \(1\text{st}\) De Morgan’s Law.

Similarly, we can verify the \(2\text{nd}\) De Morgan’s Law:

### Example 2.

Show that the statement \[s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\] is a tautology.Solution.

A tautology is defined as a proposition which is always true. So we make a truth table for the statement and check its truth values.

The values of \(p,\) \(q,\) \(\neg p,\) and \(\neg q\) are easy to fill in. The next column \({p \lor \neg q}\) means disjunction of \(p\) and \(\neg q.\) Then we find conjunction \({\neg p \land q}.\) The final statement \(s\) is disjunction of two previous propositions.

We see that all \(4\) values in the last column are true. Hence, the statement \(s = \left( {p \lor \neg q} \right) \lor \left( {\neg p \land q} \right)\) is a tautology.

### Example 3.

Show that the statement \[r = (\neg p \land q) \land (p \leftrightarrow q)\] is a contradiction.Solution.

A contradiction is a statement that is always false. Let’s construct a truth table to make sure that the statement \(r\) has only false values.

The first expression \(\neg p \land q\) is conjunction of \(\neg p\) and \(q.\) The second expression \(p \leftrightarrow q\) is the biconditional of \(p\) and \(q\). The final operation is conjunction of two previous propositions.

The last column contains only false values. Hence, the proposition \(r = (\neg p \land q) \land (p \leftrightarrow q)\) is a contradiction.

### Example 4.

Prove the distributive law \[p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).\]Solution.

We construct a truth table to make sure that the left hand and right hand sides of the statement are equivalent.

Let’s denote

\[{s1 = p \lor \left( {q \land r} \right),\;\;}\kern0pt{s2 = \left( {p \lor q} \right) \land \left( {p \lor r} \right)}\]

and find the truth values of \(s1\) and \(s2.\)

Applying conjunction and disjunction operations we get the following table:

The last two columns of the table are identical. This means that

\[{s1 \equiv s2,}\;\; \Rightarrow {p \lor \left( {q \land r} \right) \equiv \left( {p \lor q} \right) \land \left( {p \lor r} \right).}\]

### Example 5.

Let \(G\left( {x,y} \right)\) be the predicate “\(x\) goes to the gym \(y\) times a week.” Write the following propositions in predicate notation:- Nick goes to the gym \(4\) times a week.
- Nicole goes to the gym \(2\) or \(3\) times a week.
- Max goes to the gym 2 times a week, but not every week.
- Amy sometimes goes to the gym.
- Some people go to the gym every day.
- Hardly anyone goes to the gym 15 times a week.

Solution.

- Nick goes to the gym \(4\) times a week. \[G\left( {Nick,4} \right)\]
- Nicole goes to the gym \(2\) or \(3\) times a week. \[G\left( {Nicole,2} \right) \lor G\left( {Nicole,3} \right)\]
- Max goes to the gym 2 times a week, but not every week. \[G\left( {Max,2} \right) \lor G\left( {Max,0} \right)\]
- Amy sometimes goes to the gym. \[\exists y G\left( {Amy,y} \right)\]
- Some people go to the gym every day. \[\exists x G\left( {x,7} \right)\]
- Hardly anyone goes to the gym 15 times a week. \[\neg \exists x G\left( {x,15} \right)\]

### Example 6.

Suppose \(x\) is a student, \(y\) is a math course, and \(M\left( {x,y} \right)\) is the predicate “\(x\) will take \(y\)”. Translate the following sentences into predicate notation:- Every student will take Calculus.
- Every student will take a math course.
- Lora will take Calculus and Linear Algebra.
- There is a course that everybody will take.
- There is a course that nobody will take.
- Tom will take all math courses except Topology.

Solution.

- Every student will take Calculus. \[\forall x M\left( {x,Calculus} \right)\]
- Every student will take a math course. \[\forall x\exists yM\left( {x,y} \right)\]
- Lora will take Calculus and Linear Algebra. \[M\left( {Lora,Calculus} \right) \land M\left( {Lora,Linear Algebra} \right)\]
- There is a course that everybody will take. \[\exists y\forall xM\left( {x,y} \right)\]
- There is a course that nobody will take. \[\exists y\forall x\neg M\left( {x,y} \right)\]
- Tom will take all math courses except Topology. \[\forall yM\left( {Tom,y} \right) \land \neg M\left( {Tom, Topology} \right)\]

### Example 7.

Describe the following sets using set builder notation:- \(\left\{ { – 27, – 8, – 1,0,1,8,27} \right\}\)
- \(\left\{ {\large{\frac{1}{2}}\normalsize, \large{\frac{2}{3}}\normalsize, \large{\frac{3}{4}}\normalsize, \large{\frac{4}{5}}\normalsize, \large{\frac{5}{6}}\normalsize} \right\}\)
- \(\left\{ {5,8,13,21,34,55} \right\}\)

Solution.

- The set \(\left\{ { – 27, – 8, – 1,0,1,8,27} \right\}\) contains integers from \(x = -3\) to \(x = 3\) cubed. \[\left\{ {x \in \mathbb{Z}\,|\,{x^3} \text{ and } – 3 \le x \le 3} \right\}\]
- The set \(\left\{ {\large{\frac{1}{2}}\normalsize, \large{\frac{2}{3}}\normalsize, \large{\frac{3}{4}}\normalsize, \large{\frac{4}{5}}\normalsize, \large{\frac{5}{6}}\normalsize} \right\}\) contains fractions where the denominator is greater than its numerator by \(1\) and the numerator ranges from \(1\) to \(5.\) \[\left\{ {x \in \mathbb{N}\,|\,\frac{x}{{x + 1}} \text{ and } 1 \le x \le 5} \right\}\]
- The set \(\left\{ {5,8,13,21,34,55} \right\}\) is a portion of the Fibonacci sequence \({F_n}\) from \(n = 6\) to \(n = 11.\) \[{\left\{ {x \in \mathbb{N}\,|\,x \in {F_n},}\right.}\kern0pt{\left.{\text{ where } n \in \mathbb{N} \text{ and } 6 \le n \le 11} \right\}}\]