Sentence Having a Given Truth Table
Example 1: Find a sentence which has the following truth table:
| P | Q | – |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Steps:
- Mark lines which are T in the last column.
- Basic conjunction of P and Q.
- Required sentence is the disjunction of the above basic conjunctions.
| P | Q | – | Basic conjunction |
|---|---|---|---|
| T | T | T | P ∧ Q |
| T | F | T | P ∧ ~Q |
| F | T | T | ~P ∧ Q |
| F | F | F |
Required sentence: (P ∧ Q) ∨ (P ∧ ~Q) ∨ (~P ∧ Q)
Example 2
Find a sentence having the truth table below:
| P | Q | R | – |
|---|---|---|---|
| T | T | T | T |
| T | T | F | F |
| T | F | T | F |
| T | F | F | T |
| F | T | T | F |
| F | T | F | T |
| F | F | T | F |
| F | F | F | F |
Solution
| P | Q | R | – | Basic conjunction |
|---|---|---|---|---|
| T | T | T | T | P ∧ Q ∧ R |
| T | T | F | F | |
| T | F | T | F | |
| T | F | F | T | P ∧ ~Q ∧ ~R |
| F | T | T | F | |
| F | T | F | T | |
| F | F | T | F | |
| F | F | F | F |
Required sentence is (P ∧ Q ∧ R) ∨ (P ∧ ~Q ∧ ~R)
Example 3
Find a sentence having the following truth table and simplify it.
| P | Q | – |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Solution
| P | Q | – | Basic conjunction |
|---|---|---|---|
| T | T | T | P ∧ Q |
| T | F | F | |
| F | T | T | ~P ∧ Q |
| F | F | T | ~P ∧ ~Q |
The required sentence is (P ∧ Q) ∨ (~P ∧ Q) ∨ (~P ∧ ~Q)
To simplify:
(P ∧ Q) ∨ (~P ∧ Q) ∨ (~P ∧ ~Q) = (P ∧ Q) ∨ [~P ∧ (Q ∨ ~Q)] (distributive law)
= (P ∧ Q) ∨ [~P ∧ t] (complement law)
= (P ∧ Q) ∨ ~P (identity)
= (P ∨ ~P) ∧ (~P ∨ Q) (distributive)
= t ∧ (~P ∨ Q) (complement)
= ~P ∨ Q (identity)
Note: P → Q ≡ ~P ∨ Q
Questions
- For each of the following truth tables (a), (b), and (c), construct a compound sentence having that truth table.
| P | Q | R | (a) | (b) | (c) |
|---|---|---|---|---|---|
| T | T | T | T | T | F |
| T | T | F | F | T | T |
| T | F | T | T | T | T |
| T | F | F | F | T | T |
| F | T | T | F | F | F |
| F | T | F | F | F | F |
| F | F | T | F | F | F |
| F | F | F | F | F | T |
Solution
| P | Q | R | (a) | (b) | (c) | Basic conjunction of (a) | Basic conjunction of (b) | Basic conjunction of (c) |
|---|---|---|---|---|---|---|---|---|
| T | T | T | T | T | F | P ∧ Q ∧ R | P ∧ Q ∧ R | |
| T | T | F | F | T | T | P ∧ Q ∧ ~R | ||
| T | F | T | T | T | T | P ∧ ~Q ∧ R | ||
| T | F | F | F | T | T | P ∧ ~Q ∧ ~R | ||
| F | T | T | F | F | F | |||
| F | T | F | F | F | F | |||
| F | F | T | F | F | F | |||
| F | F | F | F | F | T | ~P ∧ ~Q ∧ ~R |
→ The required sentence for (a) is (P ∧ Q ∧ R) ∨ (P ∧ ~Q ∧ R)
→ The required sentence for (b) is (P ∧ Q ∧ R) ∨ (P ∧ Q ∧ ~R) ∨ (P ∧ ~Q ∧ R) ∨ (P ∧ ~Q ∧ ~R)
→ The required sentence for (c) is (P ∧ Q ∧ ~R) ∨ (P ∧ ~Q ∧ R) ∨ (~P ∧ ~Q ∧ ~R)
- i) Construct a truth table for ~ (P → Q)
- ii) Write a compound sentence having that truth table (involving ~, ∧, ∨)
- Repeat for the following sentences:
- ~P → ~Q
- ~P ∧ Q
More Questions
- Find a compound sentence having components P and Q which is true if and only if exactly one of its components P, Q is true.
- Find a compound sentence having components P, Q, and R which is true only if exactly two of P, Q, and R are true.
- Give an example of a sentence having one component which is always true.
- Give an example of a compound sentence having one component which is always false.
- Use laws of algebra of propositions to simplify ~ (P ∨ Q) ∧ (~P ∧ Q).
- Show that P → Q and ~P ∨ Q are logically equivalent.
- If Apq = P ∧ Q and Np = ~P, write the following without ~ and ∧:
- ~ (P ∧ Q)
- ~ (P ∧ ~Q)
- ~ (~P ∧ Q)
- ~ (P ∧ ~Q)
Questions
- Rewrite the following without using the conditional:
- If it is cold, he wears a hat.
- If productivity increases, then wages rise.
- Determine the truth value of the following:
- 2 + 2 = 4 if and only if 3 + 6 = 9
- 2 + 2 = 4 if and only if 5 + 1 = 2
- 1 + 1 = 2 if and only if 3 + 2 = 8
- 1 + 2 = 5 if and only if 3 + 1 = 4
- Prove by truth table:
- ~ (P → Q) ≡ P ∧ ~Q
- ~ (P → Q) ≡ ~P ∧ Q
- Prove the conditional distributes over conjunction, i.e., [P → (Q ∧ R)] ≡ (P → Q) ∧ (P → R).
- Let P denote “it is cold” and Q denote “it rains”. Write the following statements in symbolic form:
- It rains only if it is cold.
- A necessary condition for it to be cold is that it rains.
- A sufficient condition for it to be cold is that it rains.
- It never rains when it is cold.
- Write the inverse of the converse of the conditional “If a quadrilateral is a square then it is a rectangle”.
- Write the inverse of the converse of the contrapositive of “If the diagonals of the rhombus are perpendicular then it is a square”.
Logical Implications
A proposition P is said to logically imply a proposition Q if P → Q is a tautology.
Example
Show that P logically implies P ∨ Q.
Solution: Construct a truth table for P → (P ∨ Q).
| P | Q | P ∨ Q | P → (P ∨ Q) |
|---|---|---|---|
| T | T | T | T |
| T | F | T | T |
| F | T | T | T |
| F | F | F | T |
Since column 4 is a tautology, P logically implies P ∨ Q.
Arguments
An argument in logic is a declaration that a given set of propositions P₁, P₂, P₃, …, Pₙ called premises yields another proposition Q called a conclusion. Such an argument is denoted by P₁, P₂, …, Pₙ ⊢ Q.
Example of an argument
If I like mathematics, then I will study. Either I study or I fail. But I failed; therefore, I do not like mathematics.
Validity of an Argument
Validity of an argument is determined as follows:
- An argument P₁, P₂, …, Pₙ ⊢ Q is valid if Q is true whenever all the premises P₁, P₂, …, Pₙ are true.
- Validity of an argument is also determined if and only if the proposition (P₁ ∧ P₂ ∧ … ∧ Pₙ) → Q is a tautology.
Example
Prove whether the following argument is valid or not: P, P → Q ⊢ Q.
Solution: Draw a truth table for [(P ∧ (P → Q)) → Q].
| P | Q | P → Q | P ∧ (P → Q) | [(P ∧ (P → Q)) → Q] |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
Since column 5 is a tautology, the argument is valid.
Questions
- Use the truth table to show whether the given argument is valid or not: P → Q, Q → R ⊢ P → R.
- Symbolize the given argument and then test its validity:
If I like mathematics, then I will study. Either I study or I fail. But I failed; therefore, I do not like mathematics.
Solution:
Let P ≡ I like mathematics, Q ≡ I will study, R ≡ I fail.
Then the given argument is: P → Q, Q ∨ R, R ⊢ ~P.
Testing the validity of [(P → Q) ∧ (Q ∨ R) ∧ R] → ~P.
| P | Q | R | P → Q | Q ∨ R | (P → Q) ∧ (Q ∨ R) ∧ R | ~P | [(P → Q) ∧ (Q ∨ R) ∧ R] → ~P |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | F | F |
| T | T | F | T | T | F | F | T |
| T | F | T | F | T | F | F | T |
| T | F | F | F | F | F | F | T |
| F | T | T | T | T | T | T | T |
| F | T | F | T | T | F | T | T |
| F | F | T | T | T | T | T | T |
| F | F | F | T | F | F | T | T |
Since column 8 is not a tautology, the given argument is not valid.
Questions
- Translate the following arguments in symbolic form and then test their validity:
- If London is not in Denmark, then Paris is not in France. But Paris is in France, therefore London is in Denmark.
- If I work, I cannot study. Either I work or I pass mathematics. I passed mathematics; therefore, I studied.
- If I buy books, I lose money. I bought books; therefore, I lost money.
- Determine the validity of:
- P → Q, ~Q ⊢ ~P
- ~P → Q, P ⊢ ~Q
- [P → ~Q], R → Q, R ⊢ ~P
Electrical Network
An electrical network is an arrangement of wires and switches that accomplish a particular task, e.g., lighting a lamp, turning a motor, etc.
The figure below shows an electrical network:
When the switch P is closed, the current flows between T₁ and T₂.
The above network simplifies to the following network:
Relationship between statement in logic and network
A Series and Parallel Connection of Switches
A series connection of switches
The following switches are connected in series:
The current flows between T₁ and T₂ when both switches are closed, i.e., when P ∧ Q is true.
A parallel connection of switches
The current will flow when either one of the switches is closed.
Current flows when P ∨ Q is true.
Example
Consider the electrical network below:
- Construct a compound statement presenting the network above.
- Find possible switch settings that will allow the current to flow between T₁ and T₂.
Solution
Note:
- Current flows between T₁ and T₂ when switch P is closed, i.e., P is true OR
- The current flows between T₁ and T₂ when switches Q and R are closed, i.e., Q ∧ R is true.
The required compound statement is P ∨ (Q ∧ R).
To find possible switch settings, draw a truth table for P ∨ (Q ∧ R):
| P | Q | R | Q ∧ R | P ∨ (Q ∧ R) | Current flows (Yes/No) |
|---|---|---|---|---|---|
| T | T | T | T | T | Yes |
| T | T | F | F | T | Yes |
| T | F | T | F | T | Yes |
| T | F | F | F | T | Yes |
| F | T | T | T | T | Yes |
| F | T | F | F | F | No |
| F | F | T | F | F | No |
| F | F | F | F | F | No |
From Statements to Network
Example
Draw a network for the statement (P ∨ Q) ∧ (R ∧ S).
Solution:
The corresponding network is shown below:
Questions
- Draw networks for the following statements:
- [P ∨ Q ∧ (R ∧ S)]
- [(P ∧ Q) ∧ (R ∨ S)]
- [P ∨ (Q ∧ S) ∨ (R ∧ T)]
- (Q ∨ (R ∨ S) ∨ P)
- [P ∨ (Q ∧ (R ∧ S))]
Complex Switches
These operate as follows:
- When one switch is closed, the other one closes also.
- When one switch is closed, the other one opens.
Refer to the diagram:
The compound relating to flow of electrical current is given by:
(P ∧ Q) ∨ [P ∧ (~Q ∨ R)]
To find possible switch settings that will allow the current to flow between T₁ and T₂:
- Draw a truth table for (P ∧ Q) ∨ [P ∧ (~Q ∨ R)].
| P | Q | R | P ∧ Q | ~Q | ~Q ∨ R | P ∧ (~Q ∨ R) | (P ∧ Q) ∨ [P ∧ (~Q ∨ R)] |
|---|---|---|---|---|---|---|---|
| T | T | T | T | F | T | T | T |
| T | T | F | T | F | F | F | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | F | F | T | F | F |
| F | T | F | F | F | F | F | F |
| F | F | T | F | T | T | F | F |
| F | F | F | F | T | T | F | F |
Possible switch settings
| P | Q | R |
|---|---|---|
| Closed | Closed | Closed |
| Closed | Closed | Open |
| Closed | Open | Closed |
| Closed | Open | Open |
| Open | Closed | Closed |
| Open | Closed | Open |
| Open | Open | Closed |
| Open | Open | Open |
Example
Without using a truth table, draw a sample network for the statement:
(P ∧ Q) ∨ [P ∧ (~Q ∨ R)]
Solution
(P ∧ Q) ∨ [P ∧ (~Q ∨ R)] = P ∧ (Q ∨ (~Q ∨ R)) (distributive law)
= P ∧ ((Q ∨ ~Q) ∨ R) (associative law)
= P ∧ (t ∨ R) (complement law)
= P ∧ t (identity)
= P (identity)
The statement simplifies to P.
The corresponding network is as follows:
For a statement which on simplifying ends upon F, the network drawn is as follows:
For a statement which upon simplifying yields to T, the network is drawn as follows:
Questions
- For each of the networks shown below, find a compound statement that represents it.
- For each of these sentences, draw a simple network:
- P ∧ (~Q → ~P)
- ~(P ∨ Q) → R
- P ∧ ~P
- Given a truth table:
| P | Q | R | – |
|---|---|---|---|
| T | T | T | F |
| T | T | F | T |
| T | F | T | T |
| T | F | F | T |
| F | T | T | T |
| F | T | F | T |
| F | F | T | T |
| F | F | F | T |
4 Comments