1.1 Propositions and truth tables

1.1.1 Definition

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both. We use conventional letters for propositional values such as p, q, r,…. The truth value of a proposition is true, denoted by T, if it is a true proposition, while the truth value is false, denoted by F, if it is a false proposition.

1.1.2 Example

The sentence P: “Paris is the capital of France” is a true (T) proposition.
While the sentence q: “1+2=4” is a false proposition.
The sentences: (i) Do you knew where is Cairo?
(ii) Come in!
(iii) x^2-1=4
are not propositions.

1.1.3 Definition

Let p be a proposition. The negation of p, denoted by ~p, is the statement “It is not the case that p”. The proposition ~p is read “not p” or “negation p”.

1.1 Propositions and truth tables

The truth values of ~p are the opposite of the truth values of p.

In mathematics we usually have compound propositions such as “If x is an odd integer and y is an even integer then x+y is an odd integer”.

The truth values of a compound proposition depend on the truth values of the combined propositions. A table giving truth values for a compound proposition is called “a truth table”.

The following table is the truth table of ~p:

1.1 Propositions and truth tables

1.1.4 Example

Give the negation of (i) p: It is hot.
(ii)q: 2 is a divisor of 5.

Solution

(i) ~p: It is not the case that it is hot i.e. it is not hot.
(ii)~q: It is not the case that 2 is a divisor of 5 i.e. 2 is not a divisor of 5. Obviously q is false and ~q is true.

1.1.5. Definition

Let p and q be propositions. The “conjunction” of p and q, denoted by p˄q, is the proposition “p and q”. The disjunction of p and q, denoted by p˅q, is the proposition “p or q”.

The following tables display the truth tables for p˄q and p˅q. Each table has a row for each of the four possible combinations of truth values of p and q.

1.1 Propositions and truth tables

Remark

A compound proposition may have many components (propositions). For example p˅(q˄r) involves three propositions p, q and r. since each of these propositions may be independently true or false then there are 2³=8 possibilities for the truth values of p, q and r. Thus in investigating the truth values of the proposition p˅(q˄r) we form a truth table with 8 rows. In general if a compound proposition consists of n proposition then its truth table will have 2ⁿ rows.

Definition

The compound propositions p and q are called logically equivalent (denoted by p = q) if and only if the columns giving their truth values agree. A compound proposition that is always true is called “a tautology”. A compound proposition that is always false is called “a contradiction”. A compound proposition that is neither a tautology nor a contradiction is called “a contingency”.

1.1.8. Example

Prove that if p is a proposition then
(i) p˄~p is a contradiction
(ii) p˅~p is a tautology

1.1 Propositions and truth tables

1.1.8. Example

We form the following truth table

It is clear that p˄~p is always false and p˅~p is always true and we have done.

1.1.9. Example

Prove the following De Morgan’s laws:
(i) ~(p˄q)=~p˅~q
(ii) ~(p˅q)=~p˄~q

1.1 Propositions and truth tables

Solution

We construct the truth table as follows:

It comparing the truth values of ~(p˅q) and ~p˄~qwe easily observe that ~(p˅q)=~p˄~q.

(ii) similar to (i).

1.1.10 Definition
let p and q be propositions. “The conditional” statement “p→q” is the proposition “if p then q”. A conditional statement p→q is also called an “implication”. In the conditional statement p→q, p is called the hypothesis (or antecedent or presimse) and q is called the conclusion (or consequence). “The biconditional” statement “p↔q” is the proposition “p if and only if q”.

1.1 Propositions and truth tables

The truth tables for the conditional and the biconditional statements are given by table 4 and table 5, respectively.

1.1.11. We will encounter the following ways to express the conditional statement p→q:

1.1 Propositions and truth tables

(i) If p then q	(ii) p implies q
(iii) p only if q	(iv) p is sufficient for q
(v) q if p	(vi) q whenever p
(vii) q when p	(viii) q is necessary for p
(ix) q unless ~p	(x) q follows from p

1.1.12. Example. Show that

p˅(q˄r)=(p˅q)˄(p˅r)

This is “the distribution law” of disjunction over conjunction.

Solution: the required logical equivalence is obvious from the following truth table:

1.1 Propositions and truth tables

1.1.14 Example

Show that (p˄q)→(p˅q) is a tautology.

Solution

To show that this statement is a tautology, we will use logical equivalences to demonstrate that it is logically equivalent to T. (Note: This could also be done using a truth table.)

1.1 Propositions and truth tables

1.1.16 Example

Translate the following English sentence into a logical expression:
“You can access the internet from campus only if you are a computer science major or you are not a freshman”

Solution

Consider the following propositions
p is the proposition “you can access the internet from campus”
q is the proposition “you are a computer science major”
r is the proposition “you are a freshman”

Note that the proposition a→b is the proposition “a only if p”, thus the given sentence is equivalent to the following proposition:

1.1 Propositions and truth tables

1.1.17 Remark

Translating sentences into logical expressions is an essential part of specifying both hardware and software systems. System and software engineers take requirements in natural languages and produce precise specifications that can be used as the basis for system development. System specifications are called “consistent” if they don’t contain conflicting requirements that could be used to derive a contradiction. When specifications are not consistent there would be no way to develop a system that satisfies all specifications.

1.1.18 Example

(i)Determine whether these system specifications are consistent:

“The diagnostic message is stored in the buffer or it is retransmitted”
“The diagnostic message is not stored in the buffer”
“If the diagnostic message is stored in the buffer then it is retransmitted”

(ii) If the specification “The diagnostic message is not retransmitted” is added to the system specification in (i).
Do the system specifications remain consistent?

Solution
(i) Let p denotes the proposition

1.1 Propositions and truth tables

“The diagnostic message is stored in the buffer”
and q denotes “The diagnostic message is retransmitted”.

The given specifications are p˅q, ~p, p→q. Consider the following truth table.

It is clear that the specifications are all true when p is false and q is true, thus the specifications are consistent.

(ii) It is clear from the above truth table that p˅q, ~p, p→q,and ~q are not all true for all truth values of p and q, thus the system specifications are inconsistent.