Mathematical Logic

Propositional and Predicate Logic:

A proposition is a statement that can either be true (denoted T) or false (denoted F).

• Propositions can be combined using logical operators not (¬), or (∨), and (∧), implies
(→), and if and only if (↔), to create new propositions.

• Two formulas/propositions P and Q are logically equivalent (denoted P ≡ Q) if they

have the same meaning. That is, P and Q evaluate to the same value in all rows of a
truth table, or the formula P ↔ Q evaluates to T in all rows of a truth table.

• The contrapositive of an implication P → Q is the formula (¬Q) → (¬P). The

contrapositive (¬Q) → (¬P) is logically equivalent to P → Q. The converse of an
implication P → Q is the formula Q → P.

• Predicates can either be universally quantified (∀x P(x)) or existentially quantified (∃x
P(x)) to create propositions from predicates. Formulas can have multiple quantifiers
and the order in which they appear can influence their meaning.

• A domain of discourse identifies the set over which predicate variables take values
and the meaning of predicates. It plays an important role in determining the truth of
propositions.

Definition 1 (Propositions). A proposition is a statement that can either be true or

false. We will denote true as T and false as F. Let us look at some examples and non-
examples of propositions.

Example : The following statements are all propositions because they are either true
or false: “5 is prime”; “Champaign is the capital of Illinois”. On the other hand,
questions like “When is this going to end?” or commands like “Read these notes!” are
not propositions.

Logical Operators:

Propositions can be combined using logical operators to create more complex

propositions.
The negation of a proposition P is written ¬P and read “not P”.
Figure 1 shows that truth table for ¬P, which shows that ¬P takes the value T
when P is F, and takes the value F when P is T. The disjunction of propositions P
and Q.
is written P ∨ Q and read “P or Q”. The meaning of P ∨ Q is given by truth table shown in
Figure 2 — P ∨ Q evaluates to F if both P and Q are both F, and it evaluates to T in all
other cases. It is worth noting that P ∨ Q evaluates to T when both P and Q are T. Thus it
corresponds to an “inclusive or”. Another important logical operator is conjunction, written
as P ∧ Q and read “P and Q”. The truth table for P ∧ Q (Figure 3) shows that this is T
only in the case when both P and Q are T. In all other cases, P ∧ Q is F.
The next important logical operator is implication, which is writ- ten as P → Q and read
as “P implies Q”. P is the antecedent of the implication, and Q is the consequent. The
truth table for P → Q is shown in Figure 4.

Definition 3 (Contrapositive and Converse). The contrapositive of an implication P → Q is the

formula (¬Q) → (¬P). The converse of an implication P → Q is the formula Q → P.

Logical Equivalence: Logical propositions that look different may have the
same meaning. This leads to the notion of logical equivalence.

Definition 4 (Logical Equivalence). Two formulas or propositions P and Q are said to

be logically equivalent (denoted P ≡ Q) if they have the same meaning.

Commonly used Equivalences :

Equivalences between formulas are quite often
used in sim- plifying mathematical statements,
and in writing proofs. We list some commonly
used equivalences. Constructing truth tables to
demonstrate these equivalences, is left for the
reader as an exercise. In each of the
equivalences below P, Q, R are any propositions.
1. Double Negation: ¬¬P ≡ P

2. The following two equivalences hold

P ∨ (¬P) ≡ T P ∧ (¬P) ≡ F

3. Identity: The following hold.

P∨F ≡ P P ∧T ≡ P

4. Commutativity: The logical operators ∨ and ∧

are commu- tative. That is,

P∨Q ≡ Q∨P P∧Q ≡ Q∧P

5. Idempotence: The logical operators ∧ and ∨ are

idempotent. That is,
P∨P ≡P P∧P ≡ P

6. Associativity: The logical operators ∨ and ∧

are associative. That is,
 P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R

7. Distributivity: The logical operators ∨ and ∧ distribute

over each other.
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R)

P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
8. de Morgan’s Laws: These are two of the most important
equivalences that relate negation, conjunction, and disjunc- tion.
¬(P ∨ Q) ≡ (¬P) ∧ (¬Q)
¬(P ∧ Q) ≡ (¬P) ∨ (¬Q)

Combining this with the law of double negation, de Mor- gan’s Laws can be
seen as a way to define conjunction in terms of disjunction and negation (or
disjunction using conjunction and negation). Thus, we could say,

P ∨ Q ≡ ¬((¬P) ∧ (¬Q))

P ∧ Q ≡ ¬((¬P) ∨ (¬Q))

9. Implication: Implication can be defined in terms of disjunction and

negation. That is, P → Q ≡ (¬P) ∨ Q. Thus, using de Morgan’s
laws and the law of double negation, we could say ¬(P → Q) ≡ P
∧ (¬Q).

10. Contrapositive: The contrapositive of an implication is equivalent to the implication.

That is P → Q ≡ (¬Q) → (¬P).

 Predicate Logic
Predicate Logic :
Predicates are properties, additional information to better express the subject of the
sentence. A quantified predicate is a proposition , that is, when you assign values to
a predicate with variables it can be made a proposition.
For example :
In P(x) : x>5, x is the subject or the variable and ‘>5’ is the predicate.
P(7) : 7>5 is a proposition where we are assigning values to the variable x, and it has
a truth value, i.e. True.
The set of values that the variables of the predicate can assume is called the
Universe or Domain of Discourse or Domain of Predicate.
A predicate is a proposition that depends on the value of some variables. For
example, the statement “x is prime” will either be true or false depending on the value
of x. Taking the standard
interpretation for a prime number, when x = 2, the statement “x is prime” is true; and
when x = 4 the statement “x is prime” is not true. Predicates may depend on more than
one variable. For example, the
predicate Q(x, y) D= x + y = 0 depends on the values of both x and y.

Universal Quantification. It is written like an upside down A. For a predicate P,

the proposition ∀x P(x), is read as “for all x, P(x)”. This proposition is true, if the
predicate P is true not matter what value is substituted for x. Based on this
interpretation, one can observe a close correspondence between universal
quantification and conjunction. A proposition ∀x ∈ N P(x) is equivalent to saying
that P(0) is true, and P(1) is true, and P(2) is true, and so on.
Existential Quantification. The second form of quantification is existen- tial
quantification which is written like a backwards E — ∃x P(x) — and read “exists x
P(x)”. The proposition ∃x P(x) is true if there is some value we can assign to x
such that th predicate P is true.

Thus, ∃x ∈ N P(x) is effectively saying that either P(0) is true or P(1) is true or
P(2) is true and so on.
The correspondence between universal quantification and conjunc- tion, and
existential quantification and disjunction, allows one to infer logical equivalences
like de Morgan’s laws for quantification.

¬(∀x P(x)) ≡ ∃x (¬P(x))

¬(∃x P(x)) ≡ ∀x (¬P(x))

Domains of Discourse: Recall that a formula ∀x P(x) says that the predicate P is
true no matter what value is substituted for x. But where are the values drawn
from? This given by the domain of dis- course, which identifies the set over which
predicate variables take
values and the meaning of predicates. It is given explicitly in a state- ment like ∀x ∈
Z(∃y ∈ Z (x + y = 0)). Here variables x and y take values over the integers (Z). It also
tells us that + should be inter- preted the way addition is usually defined over the
integers.

Order of Quantifiers: It is important to pay attention to the order of quantifiers.

Changing the order can completely change the meaning. For example, the formula

∀x ∈ Z(∃y ∈ Z (x + y = 0))

is true, because we can take y to be −x. On the other hand,

∃y ∈ Z(∀x ∈ Z (x + y = 0))

not true — there is no number with the property that no matter what we add to it, we
get 0!
propositional equivalence:
Two compound propositions p and q are logically equivalent if p ↔ q is a
tautology. The symbol we use to show that there is a logical equivalence is ‘≡’.
As an example, p ≡ q means that p is logically equivalent to q.

Definitions

Def. A compound proposition is an expression created using propositional variables and

logical operators. Examples, p v q, p ^ q v r.

Def. A tautology is a compound proposition that is always true, with disregard of the
truth values of the propositional variables in the compound proposition.

Def. A contradiction is a compound proposition that is always false, with disregard of the
truth values of the propositional variables in the compound proposition.

Def. A contingency is a compound proposition that is not a tautology, nor a

contradiction.

Def. Two compound propositions p and q are logically equivalent if p ↔ q is a tautology.

We start with definitions because in mathematics you can’t do anything without using
definitions.

So, it is very important that you understand the definitions so you can use them to
create arguments and proofs.

Example 1: Shows the following by using a a truth table

Propositional equivalences: Example 1

If we follow the definition above that tells us if two compound propositions are logically
equivalent, we can see that by creating a truth table we can answer whether the two
compound propositions are logically equivalent or not.

I wrote another post for you in case you still don’t know how to create a truth table.
See below the table.
Propositional equivalences: Example 1 solution

As you can see, the compound proposition in the last column is a tautology because it is
always true. Then, by the definition of logical equivalence, we can state that:

There are some important logical equivalences that you can use. They are already
proved and therefore are accepted in any mathematical argument.
Logical equivalences laws
Logical equivalences for conditionals
 Logical equivalences for biconditionals

Every time you use one of these logical equivalences, you have to justify it just by
mentioning the name. In the last two cases, you justify by saying “by conditional logical
equivalence”.
1. Tautology : A propositional function which is true in every possible case.
Final column all true.
P ~P P V ~P
F T T
T F T

2. Contradiction: A propositional function which is false in every possible

case.
P ~P P V ~P
T F F
F T F

3. Contingency: A propositional function which is sometimes true and

sometimes false.
P Q ~P V Q
F F T
F T T
T F F
T T T

4. Satisfiable: It must have at least one true. [ Contingency / tautology]

5. Unsatisfiable  Contradiction
 Normal Form

In mathematical logic, a normal form is a specific representation of a logical formula

that follows a set of rules. The purpose of normal forms is to simplify the formula and
make it easier to analyze. There are many types of normal forms in mathematical logic,
but some of the most common ones include:

 Prenex normal form: A formula in prenex normal form has all its quantifiers (i.e., “for all”
and “there exists”) at the beginning of the formula.
 Conjunctive normal form: A formula in conjunctive normal form is a conjunction (i.e.,
“and”) of one or more clauses, where each clause is a disjunction (i.e., “or”) of literals.
 Disjunctive normal form: A formula in disjunctive normal form is a disjunction of one or
more clauses, where each clause is a conjunction of literals.

Together with the normal forms in propositional logic, such as disjunctive normal form or
conjunctive normal form, prenex normal form provides a canonical normal form that is
useful in automated theorem proving 12.
Normal forms are also used in other areas of mathematics, such as linear algebra and
circuit theory.

Boolean Normal Forms

There are three well established normal forms related to Boolean Expressions. We
frequently need to communicate expressions between computer programs. Having a
consistent set of normal forms makes this easier.

The three normal forms we will look at are

 Negative Normal Form (NNF)

 Conjunctive Normal Form (CNF)
 Disjunctive Normal Form (DNF)
The rules for these normal forms use some new terminology.

 Literal: a variable, constant, or negation of a variable.

 Clause: literals or expressions connected by operators.
 Disjunctive Clause: a clause created using a disjunction.
 Conjunctive Clause: a clause created using a conjunction.
It is important to differential between literals and clauses. A literal is something that
can be trivially evaluated. A clause requires all its input operands evaluated, then it
needs to be evaluated.

We also talk about where in an operator appears. We use the

words above and below in relation to operators. One operators is above another if it
gets evaluated after. One operator is below another if it gets evaluated before.

Here is an example expression with multiple operators. No operators are duplicated to

avoid confusion.
A⟹(B∨(¬C∧D))

This expression has four literals. They are A,B,¬C,D. Notice that ¬C is considered
a literal. The negation is applied directly to the variable C.

The conditional operator is above all other operators. It is the last thing that gets
evaluated. The disjunction is above the conjunction operator but below the conditional.
The conjunction is below both conditional and the disjunction, it is only above the
negation.

If we write the expression out in Racket notation, the above/below quality becomes
even more obvious.

(implies A (or B (and (not C) D)))

The code need to be evaluated from the inside out. The outermost expressions
are above the inner expressions. The terminology comes from thinking of the
expression as a tree.
Using this terminology, we can define the three common normal forms.
Predicates and Quantifiers
Predicates and quantifiers are fundamental concepts in mathematical logic. A predicate
is a statement that describes a property or characteristic of a subject. For example, the
statement “x is greater than 3” is a predicate, where “x” is the subject and “is greater
than 3” is the predicate. A quantifier is used to express the extent to which a predicate is
true over a range of elements. There are two types of quantifiers: universal and
existential.
Universal quantification is used to express that a property is true for all values of a
variable in a particular domain. For example, the statement “For all x, x is greater than
3” is an example of universal quantification. The universal quantification of P(x) for a
particular domain D is the proposition that asserts that P(x) is true for all values of x in
D.
Existential quantification, on the other hand, asserts that there exists at least one
element in the domain for which the property holds true. For example, the statement
“There exists an x such that x is greater than 3” is an example of existential
quantification.
Predicate logic extends propositional logic by adding the concept of predicates and
quantifiers to better capture the meaning of statements that cannot be adequately
expressed by propositional logic. It allows us to reason about properties that hold for all
or some elements in a domain.

A propositional function, or a predicate, in a variable x is a sentence p(x) involving x that

becomes a proposition when we give x a definite value from the set of values it can
take. We usually denote such functions by p(x), q(x), etc.

So, if p(x) is ‘x > 5’, then p(x) is not a proposition. But when we give x particular values,
say x = 6 or x = 0, then we get propositions. Here, p(6) is a true proposition and p(0) is a
false proposition.

Note: that a predicate is usually not a proposition. But, of course, every proposition is a
prepositional function in the same way that every real number is a real-valued function,
namely, the constant function.
Now, can all sentences be written in symbolic from by using only the logical
connectives? What about sentences like ‘x is prime and x + 1 is prime for some x.’?
How would you symbolize the phrase ‘for some x’, which we can rephrase as ‘there
exists an x’? You must have come across this term often while studying mathematics.
We use the symbol ‘∃’ to denote this quantifier, ‘there exists’. The way we use it is, for
instance, to rewrite ‘There is at least one child in the class.’ as‘(∃ x in U)p(x)’, where p(x)
is the sentence ‘x is in the class.’ and U is the set of all children.

Now suppose we take the negative of the proposition we have just stated. Wouldn’t it be
‘There is no child in the class.’? We could symbolize this as ‘for all x in U, q(x)’ where x
ranges over all children and q(x) denotes the sentence ‘x is not in the class.’, i.e., q(x) ≡
~ p(x).

We have a mathematical symbol for the quantifier ‘for all’, which is ‘∀’. So the
proposition above can be written as ‘(∀ x ∈ U)q(x)’, or ‘q(x), ∀ x ∈ U’.

An example of the use of the existential quantifier is the true statement. (∃ x ∈ R) (x + 1

> 0), which is read as ‘There exists an x in R for which x + 1 > 0.’.

Another example is the false statement(∃x ∈N)(x−1/2=0), which is read as ‘There exists
an x in N for which x−12=0x−21=0’.

Well-formed formula
A statement formula is an expression which is a string consisting of variables,
parentheses and connective symbol is called well-formed formula (wff).

Rules of Well-formed formula

A well-formed formula can be generated by the following rules.
(i) A statement variable standing alone is wff.
(ii) If A is a wff then ~A is a wff.
(iii) If A and B are wff, then (A˄B), (A˅B), (A→B) and (A↔B) are wff.
(iv) A string of symbols containing the statement variables, connectives and
parentheses is a wff if and only if it can be obtained by finitely many
applications of the rules (i), (ii) and (iii).

Examples of some Well-formed formula

(i) ∼(P∧Q)
(ii) ∼(P∨Q)
(iii) (P→(P∨Q))
(iv) (P→(Q→P))
(v) (((P→Q)∧(Q→R))↔(P→R))
Examples of some not Well-formed formula
(i) ∼P∧Q
(ii) (P→Q)→(∼Q)
(iii)(P→Q
(iv) (P→Q)→Q)
Types of quantification or scopes:
1. Universal(∀) – The predicate is true for all values of x in the domain.
2. Existential(∃) – The predicate is true for at least one x in the domain.
To know the scope of a quantifier in a formula, just make use of Parse trees.
Two quantifiers are nested if one is within the scope of the other.
 Example-1:
∀x ∃y (x+y=5)
Here ‘∃’ (read as-there exists) and ‘∀’ (read as-for all) are quantifiers
for variables x and y.
The statement can be represented as-
∀x Q(x)
Q(x) is ∃y P(x, y) Q(x)-the predicate is a function of only x because
the quantifier applies only to variable x.
P(x, y) is (x + y = 5)
Example to convert a statement into a nested quantifiers formula:
“There is a pupil in this lecture who has taken at least one course in Discrete
Maths.”
A statement consists of quantifiers and predicates, split it into it's two
constituents.
Here x and y are the pupil and the course and their respective quantifiers are
attached in front of them.
Write it down as-
For some x pupil, there exist a course in Discrete Maths such that x has taken
y.
∃x ∃y P (x, y), where P (x, y) is "x has taken y".
 Theorem-1: The order of nested existential quantifiers can be
changed without changing the meaning of the statement.
 Theorem-2: The order of nested universal quantifiers can be changed
without changing the meaning of the statement.
 Example-3:
Assume P(x, y) is xy=8,
∃x ∃y P(x, y) domain: integers
Translates to-
There is an integer x for which there is an integer y such that xy = 8,
which is same as-
There is a pair of integers x, y for which xy = 8.
Meaning ∃x ∃y P(x, y) is equivalent to ∃y ∃x P(x, y).
Similarly,
Assume P(x, y) is (xy = yx).
∀x ∀y P(x, y) domain: real numbers
Translates to-
 For all real numbers x, for all real numbers y, xy = yx or,
For every pair of real numbers x, y, xy = yx.
again ∀x ∀y P(x, y) is equivalent to ∀y ∀x P(x, y).
However, when the nested quantifiers are not same, changing the
order changes meaning of statement.
Negation of nested quantifiers:
 Theorem-3
To negate a sequence of nested quantifiers, you change each
quantifier in the sequence to the other type and then negate the
predicate.
So the negation of ∀x ∃y : P(x, y) is ∃x ∀y : ~P(x, y)
 Example-5:
“ ∃x at Cornell, x is at least 18 years old.”
To disagree with this, you’re negating the statement by flipping the ∃
to ∀ and then
negating the predicate:
“ ∀x at Cornell such that x is not at least 18 years old.”
Rules of Inference
Important Definitions :
1. Argument – A sequence of statements, premises, that end with a
conclusion.
2. Validity – A deductive argument is said to be valid if and only if it takes a
form that makes it impossible for the premises to be true and the conclusion
nevertheless to be false.
3. Fallacy – An incorrect reasoning or mistake which leads to invalid
arguments.
Structure of an Argument : As defined, an argument is a sequence of
statements called premises which end with a conclusion.

Rules of Inference : Simple arguments can be used as building blocks to

construct more complicated valid arguments. Certain simple arguments that
have been established as valid are very important in terms of their usage.
These arguments are called Rules of Inference. The most commonly used
Rules of Inference are tabulated below –