UNIT 4

Propositional & Predicate Logic: Propositions, Truth Tables, Tautology, Contradiction, Algebra of propositions, Theory of Inference and Natural Deduction. Theory of predicates, First order predicate, quantifiers.

PROPOSITIONAL

Many algorithms and proofs use logical expressions such as: “IF p THEN q” or “If p1 AND p2, THEN q1 OR q2” Therefore it is necessary to know the cases in which these expressions are TRUE or FALSE, that is, to know the “truth value” of such expressions.We discuss these issues in this chapter. We also investigate the truth value of quantified statements, which are statements which use the logical quantifiers “for every” and “there exist.”

PROPOSITIONS AND COMPOUND

STATEMENTS A proposition (or statement) is a declarative statement which is true or false, but not both. Consider, for example, the following six sentences:
(i) Ice floats in water. (iii) 2 + 2 = 4 (v) Where are you going?
(ii) China is in Europe. (iv) 2 + 2 = 5 (vi) Do your homework.
The first four are propositions, the last two are not. Also, (i) and (iii) are true, but (ii) and (iv) are false.

Compound Propositions Many propositions are composite, that is, composed of subpropositions and various connectives discussed subsequently. Such composite propositions are called compound propositions.Aproposition is said to be primitive if it cannot be broken down into simpler propositions, that is, if it is not composite. For example, the above propositions (i) through (iv) are primitive propositions. On the other hand, the following two propositions are composite: “Roses are red and violets are blue.” and “John is smart or he studies every nill. The fundamental property of a compound proposition is that its truth value is completely determined by the truth values of its subpropositions together with the way in which they are connected to form the compound propositions. The next section studies some of these connectives.

BASIC LOGICAL OPERATIONS

This section discusses the three basic logical operations of conjunction, disjunction, and negation which correspond, respectively, to the English words “and,” “or,” and “not.” Conjunction, p ∧ q Any two propositions can be combined by the word “and” to form a compound proposition called the conjunction of the original propositions. Symbolically, p ∧ q

EXAMPLE:-

Consider the following four statements:
(i) Ice floats in water and 2 + 2 = 4. (iii) China is in Europe and 2 + 2 = 4.
(ii) Ice floats in water and 2 + 2 = 5. (iv) China is in Europe and 2 + 2 = 5.
Only the first statement is true. Each of the others is false since at least one of its substatements is false. Disjunction, p ∨ q Any two propositions can be combined by the word “or” to form a compound proposition called the disjunction of the original propositions. Symbolically, p ∨ q
read “p or q,” denotes the disjunction of p and q.

TRUTH TABLE

A truth table is a mathematical table used in logic—specifically in connection with Boolean algebra, boolean functions, and propositional calculus—which sets out the functional values of logical expressions on each of their functional arguments, that is, for each combination of values taken by their logical variables (Enderton, 2001). In particular, truth tables can be used to show whether a propositional expression is true for all legitimate input values, that is, logically valid.
A truth table has one column for each input variable (for example, P and Q), and one final column showing all of the possible results of the logical operation that the table represents (for example, P XOR Q). Each row of the truth table contains one possible configuration of the input variables (for instance, P=true Q=false), and the result of the operation for those values. See the examples below for further clarification. Ludwig Wittgenstein is often credited with inventing the truth table in his Tractatus Logico-Philosophicus,[1] though it appeared at least a year earlier in a paper on propositional logic by Emil Leon Post.[2] Logical true[edit] The output value is always true, regardless of the input value of p
Logical True
p T
T T
F T
Logical false[edit] The output value is never true: that is, always false, regardless of the input value of p
Logical False
p F
T F
F F
Logical identity[edit] Logical identity is an operation on one logical value p, for which the output value remains p. The truth table for the logical identity operator is as follows:
Logical Identity
p p
T T
F F
Logical negation[edit] 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, Np, Fpq, or ~p) is as follows:
Logical Negation
p ¬p
T F
F T
Binary operations[edit] There are 16 possible truth functions of two binary variables:
Truth table for all binary logical operators[edit] Here is an extended truth table giving definitions of all possible truth functions of two Boolean variables P and Q:[note 1]
P Q F0 NOR1 Xq2 ¬p3 ↛4 ¬q5 XOR6
NAND7 AND8 XNOR9 q10 if/then11 p12 then/if13 OR14 T15
T T F F F F F F F F T T T T T T T
T F F F F F T T T T F F F F T T T
F T F F T T F F T T F F T T F F T
F F F T F T F T F T F T F T F T F T
Com ✓ ✓ ✓ ✓ ✓ ✓ ✓ ✓
L id F F T T T,F T F R id F F T T T,F T F where
T = true. F = false.
The Com row indicates whether an operator, op, is commutative - P op Q = Q op P. The L id row shows the operator's left identities if it has any - values I such that I op Q = Q. The R id row shows the operator's right identities if it has any - values I such that P op I = P.[note 2] The four combinations of input values for p, q, are read by row from the table above. The output function for each p, q combination, can be read, by row, from the table.

Key:
The following table is oriented by column, rather than by row. There are four columns rather than four rows, to display the four combinations of p, q, as input.
p: T T F F
q: T F T F
There are 16 rows in this key, one row for each binary function of the two binary variables, p, q. For example, in row 2 of this Key, the value of Converse nonimplication (' {\displaystyle \nleftarrow } \nleftarrow ') is solely T, for the column denoted by the unique combination p=F, q=T; while in row 2, the value of that ' {\displaystyle \nleftarrow } \nleftarrow ' operation is F for the three remaining columns of p, q. The output row for {\displaystyle \nleftarrow } \nleftarrow is thus
2: F F T F and the 16-row[3] key is
operator Operation name
0 (F F F F)(p, q) Contradiction
1 (F F F T)(p, q) Logical NOR
2 (F F T F)(p, q) Converse nonimplication
3 (F F T T)(p, q) Negation
4 (F T F F)(p, q) Material nonimplication
5 (F T F T)(p, q) ¬q Negation
6 (F T T F)(p, q) Exclusive disjunction
7 (F T T T)(p, q) NAND Logical NAND
8 (T F F F)(p, q) AND Logical conjunction
9 (T F F T)(p, q) XNOR Logical biconditional
10 (T F T F)(p, q) Projection function
11 (T F T T)(p, q) Material implication
12 (T T F F)(p, q) Projection function
13 (T T F T)(p, q) Converse implication
14 (T T T F)(p, q) Logical disjunction
15 (T T T T)(p, q) Tautology
Logical operators can also be visualized using Venn diagrams.
Logical conjunction (AND) 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, Kpq, p & q, or p {\displaystyle \cdot } \cdot q) is as follows:
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 (OR)[edit] 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, Apq, 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 Stated in English, if p, then p ∨ q is p, otherwise p ∨ q is q.
Logical implication[edit]
Logical implication and the material conditional are both associated with an operation on two logical values, typically the values of two propositions, which produces a value of false if the first operand is true and the second operand is false, and a value of true otherwise.
The truth table associated with the logical implication p implies q (symbolized as p ⇒ q, or more rarely Cpq) is as follows:
Logical Implication
p q p ⇒ q
T T T
T F F
F T T
F F T
The truth table associated with the material conditional if p then q (symbolized as p → q) is as follows:
Material Conditional
p q p → q
T T T
T F F
F T T
F F T
It may also be useful to note that p ⇒ q and p → q are equivalent to ¬p ∨ q.
Logical equality[edit] 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, Epq, p = q, or p ≡ q) is as follows:
Logical Equality
p q p ↔ q
T T T
T F F
F T F
F F T
So p EQ q is true if p and q have the same truth value (both true or both false), and false if they have different truth values.
Exclusive disjunction[edit] Exclusive disjunction is an operation on two logical values, typically the values of two propositions, that produces a value of true if one but not both of its operands is true.
The truth table for p XOR q (also written as p ⊕ q, Jpq, p ≠ q, or p ↮ q) is as follows:
Exclusive Disjunction
p q p ⊕ q
T T F
T F T
F T T
F F F
For two propositions, XOR can also be written as (p ∧ ¬q) ∨ (¬p ∧ q).
Logical NAND[edit] 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, Dpq, or p | q) is as follows:
Logical NAND
p q p ↑ q
T T F
T F T
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.

TAUTOLOGIES

Some propositions P(p, q, . . .) contain only T in the last column of their truth tables or, in other words, they are true for any truth values of their variables. Such propositions are called tautologies.

Analogously, a proposition P(p, q, . . .) is called a contradiction if it contains only F in the last column of its truth table or, in other words, if it is false for any truth values of its variables. For example, the proposition “p or not p,” that is, p ∨¬p, is a tautology, and the proposition “p and not p,” that is, p∧¬p, is a contradiction. This is verified by looking at their truth tables in Fig. 4-5. (The truth tables have only two rows since each proposition has only the one variable p.)
Note that the negation of a tautology is a contradiction since it is always false, and the negation of a contradiction is a tautology since it is always true.
Now let P(p, q, . . .) be a tautology, and let P1(p, q, . . .), P2(p, q, . . .), . . . be any propositions. Since P(p, q, . . .) does not depend upon the particular truth values of its variables p, q, . . ., we can substitute P1 for p, P2 for q, . . . in the tautology P(p, q, . . .) and still have a tautology. In other words: Theorem 4.1 (Principle of Substitution): If P(p, q, . . .) is a tautology, then P(P1, P2, . . .) is a tautology for any propositions P1, P2, . . ..

LOGICAL EQUIVALENCE

Two propositions P(p, q, . . .) and Q(p, q, . . .) are said to be logically equivalent, or simply equivalent or equal, denoted by
P(p, q, . . .) ≡ Q(p, q, . . .) if they have identical truth tables. Consider, for example, the truth tables of ¬(p ∧ q) and ¬p∨¬q appearing in
Observe that both truth tables are the same, that is, both propositions are false in the first case and true in the other three cases. Accordingly, we can write ¬(p ∧ q) ≡ ¬p ∨¬q
In other words, the propositions are logically equivalent.
Remark: Let p be “Roses are red” and q be “Violets are blue.” Let S be the statement:
“It is not true that roses are red and violets are blue.” Then S can be written in the form ¬(p ∧ q). However, as noted above, ¬(p ∧ q) ≡ ¬p ∨ ¬q. Accordingly, S has the same meaning as the statement: “Roses are not red, or violets are not blue.”

CONTRADICTIONS


Some propositions P(p, q, . . .) contain only T in the last column of their truth tables or, in other words, they are true for any truth values of their variables. Such propositions are called tautologies. Analogously, a proposition P(p, q, . . .) is called a contradiction if it contains only F in the last column of its truth table or, in other words, if it is false for any truth values of its variables. For example, the proposition “p or not p,” that is, p ∨¬p, is a tautology, and the proposition “p and not p,” that is, p∧¬p, is a contradiction. This is verified by looking at their truth tables in Fig. 4-5. (The truth tables have only two rows since each proposition has only the one variable p.) Note that the negation of a tautology is a contradiction since it is always false, and the negation of a contradiction is a tautology since it is always true. Now let P(p, q, . . .) be a tautology, and let P1(p, q, . . .), P2(p, q, . . .), . . . be any propositions. Since P(p, q, . . .) does not depend upon the particular truth values of its variables p, q, . . ., we can substitute P1 for p, P2 for q, . . . in the tautology P(p, q, . . .) and still have a tautology. In other words: Theorem 4.1 (Principle of Substitution): If P(p, q, . . .) is a tautology, then P(P1, P2, . . .) is a tautology for any propositions P1, P2, . . ..

LOGICAL EQUIVALENCE

Two propositions P(p, q, . . .) and Q(p, q, . . .) are said to be logically equivalent, or simply equivalent or equal, denoted by P(p, q, . . .) ≡ Q(p, q, . . .) if they have identical truth tables. Consider, for example, the truth tables of ¬(p ∧ q) and ¬p∨¬q appearing in Fig. 4-6. Observe that both truth tables are the same, that is, both propositions are false in the first case and true in the other three cases. Accordingly, we can write ¬(p ∧ q) ≡ ¬p ∨¬q In other words, the propositions are logically equivalent. Remark: Let p be “Roses are red” and q be “Violets are blue.” Let S be the statement: “It is not true that roses are red and violets are blue.” Then S can be written in the form ¬(p ∧ q). However, as noted above, ¬(p ∧ q) ≡ ¬p ∨ ¬q. Accordingly, S has the same meaning as the statement: “Roses are not red, or violets are not blue.”

ALGEBRA OF PROPOSITIONS

Propositions satisfy various laws which are listed. (In this table, T and F are restricted to the truth values “True” and “False,” respectively.)We state this result formally.
Propositions satisfy the laws of Table.

Idempotent laws:

p ∨ p ≡ p (1b) p ∧ p ≡ p

Associative laws:

(2a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (2b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

Commutative laws:

p ∨ q ≡ q ∨ p (3b) p ∧ q ≡ q ∧ p

Distributive laws:

(4a) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) (4b) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

Identity laws:

(5a) p ∨ F ≡ p (5b) p ∧ T ≡ p (6a) p ∨ T ≡ T (6b) p ∧ F ≡ F Involution law: (7) ¬¬p ≡ p

Complement laws:

(8a) p ∨¬p ≡ T (8b) p ∧¬p ≡ T (9a) ¬T ≡ F (9b) ¬F ≡ T

DeMorgan’s laws:

(10a) ¬(p ∨ q) ≡ ¬p ∧¬q (10b) ¬(p ∧ q) ≡ ¬p ∨¬q

CONDITIONAL AND BICONDITIONAL STATEMENTS


Many statements, particularly in mathematics, are of the form “If p then q.” Such statements are called conditional statements and are denoted by p → q
The conditional p → q is frequently read “p implies q” or “p only if q.” Another common statement is of the form “p if and only if q.” Such statements are called biconditional statements and are denoted by p ↔ q The truth values of p → q and p ↔ q are defined by the tables in Fig. 4-7(a) and (b). Observe that: (a) The conditional p → q is false only when the first part p is true and the second part q is false. Accordingly, when p is false, the conditional p → q is true regardless of the truth value of q. (b) The biconditional p ↔ q is true whenever p and q have the same truth values and false otherwise. The truth table of ¬p ∧q appears in Fig. 4-7(c). Note that the truth table of ¬p ∨q and p → q are identical, that is, they are both false only in the second case. Accordingly, p → q is logically equivalent to ¬p ∨ q; that is, p → q ≡ ¬p ∨ q

LOGIC AND PROPOSITIONAL CALCULUS


In other words, the conditional state/h2ment “If p then q” is logically equivalent to the statement “Not p or q” which only involves the connectives ∨ and ¬ and thus was already a part of our language.We may regard p → q as an abbreviation for an oft-recurring statement.

ARGUMENTS


An argument is an assertion that a given set of propositions P1, P2, . . . , Pn, called premises, yields (has a consequence) another proposition Q, called the conclusion. Such an argument is denoted by P1, P2, . . . , Pn $ Q The notion of a “logical argument” or “valid argument” is formalized as follows: Definition 4.4: An argument P1, P2, . . . , Pn $ Q is said to be valid if Q is true whenever all the premises P1, P2, . . . , Pn are true. An argument which is not valid is called fallacy.

EXAMPLE


(a) The following argument is valid: p, p → q $q (Law of Detachment) The proof of this rule follows from the truth table in Fig. 4-7(a). Specifically, p and p → q are true simultaneously only in Case (row) 1, and in this case q is true.
(b) The following argument is a fallacy: p → q, q $ p For p → q and q are both true in Case (row) 3 in the truth table in Fig. 4-7(a), but in this case p is false. Now the propositions P1, P2, . . . , Pn are true simultaneously if and only if the proposition P1 ∧ P2 ∧ . . . Pn is true. Thus the argument P1, P2, . . . , Pn $ Q is valid if and only if Q is true whenever P1 ∧ P2 ∧ . . . ∧ Pn is true or, equivalently, if the proposition (P1 ∧ P2 ∧ . . . ∧ Pn) → Q is a tautology.We state this result formally. Theorem 4.3: The argument P1, P2, . . . , Pn $ Qis valid if and only if the proposition (P1∧P2 . . .∧Pn) → Q is a tautology. We apply this theorem in the next example.

LOGIC AND PROPOSITIONAL CALCULUS

which reads “There exists an x in A such that p(x) is a true statement” or, simply, “For some x, p(x).” The symbol ∃ which reads “there exists” or “for some” or “for at least one” is called the existential quantifier. Statement (4.3) is equivalent to the statement Tp = {x | x ∈ A, p(x)} =  (4.4) i.e., that the truth set of p(x) is not empty. Accordingly, ∃x p(x), that is, p(x) preceded by the quantifier ∃, does have a truth value. Specifically:
Q2: If {x | p(x)} =  then ∃x p(x) is true; otherwise, ∃x p(x) is false.

EXAMPLE

(a) The proposition (∃n ∈ N)(n + 4 < 7) is true since {n | n + 4 < 7} = {1, 2} = . (b) The proposition (∃n ∈ N)(n + 6 < 4) is false since {n | n + 6 < 4} = . (c) The symbol ∃ can be used to define the union of an indexed collection {Ai | i ∈ I } of sets Ai as follows: ∪(Ai | i ∈ I) = {x | ∃ i ∈ I, x | ∈ Ai }

NEGATION OF QUANTIFIED STATEMENTS


Consider the statement: “All math majors are male.” Its negation reads: “It is not the case that all math majors are male” or, equivalently, “There exists at least one math major who is a female (not male)” Symbolically, using M to denote the set of math majors, the above can be written as ¬(∀x ∈ M)(x is male) ≡ (∃ x ∈ M) (x is not male) or, when p(x) denotes “x is male,” ¬(∀x ∈ M)p(x) ≡ (∃ x ∈ M)¬p(x) or ¬∀xp(x) ≡ ∃x¬p(x)

THEORY OF INFERRENCE


Mathematical logic is often used for logical proofs. Proofs are valid arguments that determine the truth values of mathematical statements.
An argument is a sequence of statements. The last statement is the conclusion and all its preceding statements are called premises (or hypothesis). The symbol “∴∴”, (read therefore) is placed before the conclusion. A valid argument is one where the conclusion follows from the truth values of the premises.

Example

11-10-2017Let P be the proposition, “He studies very hard” is true
Therefore − "Either he studies very hard Or he is a very bad student." Here Q is the proposition “he is a very bad student”.

Conjunction

If P and Q are two premises, we can use Conjunction rule to derive P∧QP∧Q.
PQ∴P∧Q
PQ∴P∧Q

Example

Let P − “He studies very hard”
Let Q − “He is the best boy in the class”
Therefore − "He studies very hard and he is the best boy in the class"

Simplification

If P∧QP∧Q is a premise, we can use Simplification rule to derive P.
P∧Q∴P
P∧Q∴P

Example

"He studies very hard and he is the best boy in the class", P∧QP∧Q Therefore − "He studies very hard"

Modus Ponens


If P and P→QP→Q are two premises, we can use Modus Ponens to derive Q.
P→QP∴Q P→QP∴Q

Example

"If you have a password, then you can log on to facebook", P→QP→Q "You have a password", P
Therefore − "You can log on to facebook"

Modus Tollens


If P→QP→Q and ¬Q¬Q are two premises, we can use Modus Tollens to derive ¬P¬P.
P→Q¬Q∴¬P
P→Q¬Q∴¬P

Example

"If you have a password, then you can log on to facebook", P→QP→Q "You cannot log on to facebook", ¬Q¬Q Therefore − "You do not have a password "

Disjunctive Syllogism

If ¬P¬P and P∨QP∨Q are two premises, we can use Disjunctive Syllogism to derive Q. ¬
PP∨Q∴Q
¬PP∨Q∴Q

Example

"The ice cream is not vanilla flavored", ¬P¬P
"The ice cream is either vanilla flavored or chocolate flavored", P∨QP∨Q
Therefore − "The ice cream is chocolate flavored”

Hypothetical Syllogism

If P→QP→Q and Q→RQ→R are two premises, we can use Hypothetical Syllogism to derive P→RP→R
P→QQ→R∴P→R
P→QQ→R∴P→R

Example

"If it rains, I shall not go to school”, P→QP→Q "If I don't go to school, I won't need to do homework", Q→RQ→R Therefore − "If it rains, I won't need to do homework"

THEORY OF PREDICATE


In mathematical logic, a predicate is commonly understood to be a Boolean-valued function P: X→ {true, false}, called the predicate on X. However, predicates have many different uses and interpretations in mathematics and logic, and their precise definition, meaning and use will vary from theory to theory. So, for example, when a theory defines the concept of a relation, then a predicate is simply the characteristic function or the indicator function of a relation. However, not all theories have relations, or are founded on set theory, and so one must be careful with the proper definition and semantic interpretation of a predicate. Informally, a predicate is a statement that may be true or false depending on the values of its variables.[1] It can be thought of as an operator or function that returns a value that is either true or false.

Example:-

when P is a predicate on X, one might sometimes say P is a property of X. Similarly, the notation P(x) is used to denote a sentence or statement P concerning the variable object x. The set defined by P(x) is written as {x | P(x)}, and is just a collection of all the objects for which P is true.
For instance, {x | x is a natural number less than 4} is the set {1,2,3}.
If t is an element of the set {x | P(x)}, then the statement P(t) is true.
Here, P(x) is referred to as the predicate, and x the subject of the proposition. Sometimes, P(x) is also called a propositional function, as each choice of x produces a proposition.
A simple form of predicate is a Boolean expression, in which case the inputs to the expression are themselves Boolean values, combined using Boolean operations. Similarly, a Boolean expression with inputs predicates is itself a more complex predicate.

FIRST ORDER PREDICATE



The predicate calculus includes a wider range of entities. It permits the description of relations and the use of variables. It also requires an understanding of quantification.
The language of predicate calculus requires:
Variables
Constants ---these include the logical constants
The last two logical constants are additions to the logical connectives of propositional calculus ---they are known as quantifiers. The non-logical constants include both the `names' of entities that are related and the `names' of the relations.

Example

The constant dog might be a relation and the constant fido an entity. Predicate ---these relate a number of entities. This number is usually greater than one. A predicate with one argument is often used to express a property e.g. sun(hot) may represent the statement that ``the sun has the property of being hot''. If there are no arguments then we can regard the `predicate' as standing for a statement à la the propositional calculus.
Formulæ ---these are constructed from predicates and formulæ gif. The logical constants are used to create new formulæ/ from old ones. Here are some examples:
Note that the word ``and'' used in the left hand column is used to suggest that we have more than one formula for combination ---and not necessarily a conjunction.

In the last two examples, ``dog(X)'' contains a variable which is said to be free while the ``X'' in ``X.dog(X)'' is bound.
Sentence ---a formula with no free variables is a sentence. Two informal examples to illustrate quantification follow:
The former is an example of universal quantification and the latter of existential quantification.
We can now represent the problem we initially raised: X.(dog(X)smelly(X))dog(fido)smelly(fido) To verify that this is correct requires that we have some additional machinery which we will not discuss here.

QUANTIFIERS


Let A be a given set. A propositional function (or an open sentence or condition) defined on A is an expression p(x) which has the property that p(a) is true or false for each a ∈ A. That is, p(x) becomes a statement (with a truth value) whenever any element a ∈ A is substituted for the variable x. The set A is called the domain of p(x), and the set Tp of all elements of A for which p(a) is true is called the truth set of p(x). In other words, Tp = {x | x ∈ A, p(x) is true} or Tp = {x | p(x)}

LOGIC AND PROPOSITIONAL CALCULUS

Frequently, when A is some set of numbers, the condition p(x) has the form of an equation or inequality involving the variable x.
A predicate is a sentence that contains a finite number of variables and becomes a statement when specific values are substituted for the variables. The domain of a predicate variable is the set of all values that may be substituted in place of the variable. In predicate calculus, the following 2 quantifiers are important

universal quantifier:

meaning ``for all''

existential quantifier:

meaning ``there exists''

Example

The statement that |sin (x) | 1 for any real-valued number x can be written in either of the following forms

Hence we see that the domain of a predicate could also be absorbed in the predicate itself.
Let P(x) and Q(x) be predicates (of a common domain D). We introduce the following two useful notations
A universal statement ( x D, P(x)) is true if and only if P(x) is true for every x D.
An existential statement ( x D, P(x)) is true if and only if P(x) is true for at least one x D.
P(x) Q(x) means ( x D, P(x) Q(x)) is true.
P(x) Q(x) means ( x D, P(x) Q(x)) is true.
We note that in the case of p and q being propositions, then p q simply means p q is a tautology. We also note that the predicate variable x actually represents all the predicate variables. In general a statement may involve many mathematical or logical operations. It is thus worthwhile to list a finer order of precedence parentheses.

Examples


Let be the set of natural integers, i.e. ={ 0, 1, 2, ... }. Represent mathematically the following statements.
(a) The sum or subtraction of any integers will remain an integer.
(b) An integer, if divided by an integer, may not remain an integer.
(c) There exist 2 integers such that the sum of the squares of these 2 integers can be written as the square of an integer.
(d) The sum of the squares of any 2 integers can be written as the square of an integer.

Solution

We'll explain in more details in the first 2 cases.
(a) This statement can be written in any of the following 3 forms m, n , ((m+n) ) ((m-n) ), m , n , ((m+n) ) ((m-n) ) , m , ( n , ((m+n) ) ((m-n) ) ) .
This is because essentially (m+n) says the sum of 2 integers is again an integer, and (m-n) says likewise for the subtraction of 2 integers. We note that while the 1st form is perhaps the neatest, the 1st and the 2nd forms can both be interpreted as an equivalent ``shorthand'' notation of the 3rd form. Moreover, the 3rd form can be regarded as an embedded predicate statement because the 3rd form can considered as
m , P(m) ,
where P(m) for each given m is again a predicate statement: n , ((m+n) ) ((m-n) )) .
(b) First we rephrase the original sentence in a form closer to the mathematical language. It is easy to observe that the original sentence is equivalent to ``There exist 2 integers such that the division of the 1st integer by the 2nd integer is no longer an integer''. Written symbolically, m, n , m/n .
Obviously the above form can also be written in other equivalent variant forms similar to the case (a). (c) m , n , p , m2+n2 = p2. (d) m , n , p , m2 + n2 = p2. Are the 2 statements (a) and (b) below true? (a) m , n , p , m2+n2 = p2 and m,n,p 1. (b) m , n , p , m2 + n2 = p2. Solution We note that more than 1 quantifier are used in both (a) and (b).
(a)
Though m = 0, n = 0 and p=0 satisfy m2 + n2 = p2, they do not satisfy m,n, p 1. Hence this case is not able to shed much light on the validity of the statement (a). However m=3, n=4 and p=5 satisfy both m2 + n2 = p2 and m, n, p 1. We see that (a) is true regardless of other cases of m,n and p.
(b)
For m = 0, n=0, we can choose p=0 so that m2 + n2 = p2, i.e. the predicate is true in this particular case. However, for m =1 and n=1, we see that if a p satisfies p2 = m2 + n2 = 2, then p must be . But no such nonnegative integers p satisfy p2=2. Hence (b) is false.