• ### UNIT 2 : Propositional and predicate logic

Key unit competence

Use mathematical logic to organise scientific knowledge and as a tool of reasoning in daily life.

Learning objectives

Activity 2.1

In groups of five, carry out research to distinguish between a statement and a proposition.  Give examples of statements and propositions. Present your findings in class for discussion.

A statement is a declarative sentence or descriptive sentence.  A logical proposition is a statement that has truth value. It can either be true or false, but not both.

In logic, we seek to express statements, and the connections between them in algebraic symbols. Logic propositions can be denoted by letters such as p, q, r, s, …

Below are some examples:

• r: 4 < 8

• s: If x = 4 then x + 3 = 7

• t:  Nyanza is city in Rwanda

• p: What a beautiful evening!

The statements r, s and t are logic propositions. The statement p is not a logic proposition.

Recall that a proposition is a declarative sentence that is either true or false. Here are some more examples of propositions:

• All cows are brown.

• The Earth is farther from the sun than Venus.

• 2 + 2 = 5.

Here are some sentences that are not propositions.

1. "Do you want to go to the market?”  Since a question is not a declarative sentence, it fails to be a proposition.

2. "Clean up your room.” Likewise, this is not a declarative sentence; hence, fails to be a proposition.

3. "2x = 2 + x.”  This is a declarative sentence, but unless x is assigned a value or is otherwise prescribed, the sentence is neither true nor false, hence, not a proposition.

Each proposition can be assigned one of two truth values. We use T or 1 for true and use F or 0 for false.

2.2 Propositional logic

The simplest and most abstract logic we can study is called propositional logic.

Truth tables

The true values and false values are generally called true values of a logic proposition. At each proposition, corresponds an application that is a set {True, False} denoted by {T,F} or {1,0}.

You can use truth tables to determine the truth or falsity of a complicated statement based on the truth or falsity of its simple components.

A statement in sentential logic is built from simple statements using the logical connectives ∼, ∧, ∨, ⇒ and ⇔. We can construct tables which show how the truth or falsity of a statement built with these connectives depends on the truth or falsity of its components.

Figure 2.1 is the table for negation:

This table (Figure 2.1) is easy to understand. If p is true, its negation ∼ p is false. If p is false, then ∼ p is true}.

In Figure 2.2, p ∧ q should be true when both p and q are true, and false otherwise:

In Figure 2.3, p ∨ q is true if either p is true or q is true (or both). It is only false if both p and q are false.

Figure 2.4 shows the table for logical implication:

There are 2n different possibilities of truth values given n logic propositions:

i. In the case of one proposition p there are 21 = 2 possibilities   p : T or F

ii. In the case of two propositions p and q there are 22 = 4 possibilities

iii. The case of three propositions p, q and r there are 23 = 8 possibilities

Negation of a logic proposition (statement)

Activity 2.2

You are given a statement P:I go to school. What is the negative statement?

Logical negation is represented by the operator “NOT” denoted by "∼ or ¬ ”. The negation of the proposition p is the proposition ∼p which is true if p is false and false if p is true.

For example:

1. p : The lion is a wild animal; ∼p. The lion is not a wild animal.

2. q :3 < 7; ∼q: 3 ≥ 7

Logical connectives

Activity 2.3

You are given two statements:

p:I study Maths

q:I study English.

What do you say if you combine the two statements?

Propositions are combined by means of connectives  such as and, or, if … then and if and only if and they are modified by not.

1. Conjunction

The logical conjunction is represented by the binary operator “and” denoted by "∧" . If p and q are propositions, p ∧ q is true only when both p and q are true. See Figure 2.7.

2. Disjunction

The logical disjunction is represented by the binary operator “or” denoted by “∨”. If p and q are propositions, p ∨ q is true when either p or q is true. See Figure 2.8

3. Implication

The statement “p implies q” or “if p then q”, written as “p ⇒ q” is called the implication or the conditional. In this setting, p is called “the premise, hypothesis or antecedent of the implication” and q is “the conclusion or the consequence of the implication”. p ⇒ q is false only when the antecedent p is true and the consequence q is false.

The statement p ⇒ q, when p is false, is sometimes called “a vacuous statement”. The converse of p ⇒ q is the implication q ⇒ p. If an implication is true, then its converse may or may not be true.

4. Equivalence

Statements p and q are said to be equivalent if they have the same truth table values. The corresponding logical symbols are "⇔" and “≡”, and sometimes “iff”.

The biconditional p ⇔ q read as “p is .... if and only if q” is true only when p and q have the same truth values

Note: The order of operations for the five logical connectives is as follows:

A compound statement is a tautology if its truth value is always T, regardless of the truth values of its variables. It is a contradiction if its truth value is always F, regardless of the truth values of its variables. Notice that these are properties of a single statement, while logical equivalence always relates two statements.

When a statement is a tautology, we also say that the statement is tautological. In common usage this sometimes simply means that the statement is convincing. We are using it for something stronger: the statement is always true, under all circumstances. In contrast, a contradiction, or contradictory statement, is never true, under any circumstances.

Contingency

Contingency is the status of propositions that are neither true (i.e. tautologies) nor false under every possible valuation (i.e. contradictions).

Logically equivalent proposition

Two statements X and Y are logically equivalent if X ⇔ Y is a tautology. Another way to say this is: For each assignment of truth values to the simple statements which make up X and Y, the statements X and Y have identical truth values.

From a practical point of view, you can replace a statement in a proof by any logically equivalent statement.

To test whether X and Y are logically equivalent, you could set up a truth table to test whether X ⇔ Y is a tautology; that is, whether X ⇔ Y ”has all Ts in its column”. However, it’s easier to set up a table containing X and Y and then check whether the columns for X and for Y are the same.

De Morgan’s Law For any two propositions p and q, the following hold:

1. ∼(p ∨ q)= ∼p ∧ ∼q

2. ∼(p ∧ q) = ∼p v ∼q

Given two sets A, B in the universal set U:

(A ∪ B)′ = A′ ∩ B′

(A ∩ B)′ = A′ U B′

There are an infinite number of tautologies and logical equivalences. A few examples are given below.

2.3 Predicate logic

Propositional functions

The propositional functions are propositions that contain variables i.e. a sentence expressed in a way that would assume the value of true or false, except that within the sentence there is a variable (x) that is not defined or specified, which leaves the statement undetermined.

The statements such as x+2 > 5 are declarative statements but not propositions when the variables are not specified. However, one can produce propositions from such statements. A propositional function or predicate is an expression involving one or more variables defined on some domain, called the domain of discourse. Substitution of a particular value for the variable(s) produces a proposition which is either true or false. For instance, P(x) : x+2 > 5 is a predicate on the set of real numbers. Observe that P(2) is false, P(4) is true. In the expression P(x); x is called a free variable. As x varies, the truth value of P(x) varies as well. The set of true values of a predicate P(x) is called the truth set.

Activity 2.4

Carry out research to find the meaning of a propositional function. Discuss your findings, using examples, with the rest of the class.

Logic quantifiers

a)  Universal quantifier

The universal quantifier is the symbol "∀" read as “for all” or “given any”.  It means that each element of a set verifies a given property defined on that set.

For example, consider the following equation in : 1x = x Every x that belongs to , verify the equation.  In form of equation we write ∀ x ∈ : 1x = x.

b)  Existence quantifier

The symbol “∃” read as “there exists” is called existence quantifier. It means that we can find at least an element of a set which verifies a given property defined on the set.

For example, consider the following inequality in : x + 3 < 5. In this case, x represents a range of elements which verify the inequality. In form of equation we write

∃ x ∈ , x + 3 < 5

The symbol “∃!” read as “there exists only one” is used in the case of unique existence.

Negation of logical quantifiers

Activity 2.5

In groups, consider the statement:

p: All students in this class are brown

Discuss what is required to show the statement is false by explaining and thus negate the statement.

The negation of ‘All students in this class are boys’ is ‘There is a student in this class who is not a boy’.

To negate a statement with a universal quantifier, we change a universal quantifier to the existential one and then negate the propositional function, and vice versa.

The negation of ∀ x : p is ∃ x : (~p) and the negation of ∃ x : p is ∀ x : (~p)  and thus:

~ (∀ x : p) ≡ ∃ x : (~p))

~ (∃ x : p)  ≡ ∀ x : (~p)

2.4 Applications

Activity 2.6

In pairs, carry out research on the different ways we can apply propositional and predicate logic. Discuss your findings with the rest of the class.

Set theory

Activity 2.7

Carry out research to answer the following:

What is set theory?

How is it an application in logic?

Set theory is the branch of mathematical logic that studies sets, which informally are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics.

In logic, Venn diagrams can be used to represent the truth of certain statements and also for examining logical equivalence of two or more than two statements.

Electric circuits

If in an electric network two switches are used, then the two switches S1 and S2 can be in one of the following two cases;

In series: then the current will flow through the circuit only when the two switches S1 and S2 are on (i.e. closed).

• In parallel: the current will flow through the circuit if and only if either S1 or S2 or both are on (i.e. closed)

Equivalent circuits

Two circuits involving switches S1, S2, …, are said to be equivalent if for every positions of the switches, either current passes through both the circuits, or it does not pass through either circuit.

UNIT 1 : Fundamentals of trigonometryUNIT 3 : Binary operations