Welcome to Edukum.com

Propositional Logic

Propositional Logic

Proposition and Truth Function
A proposition is a declarative statement which is either true or false but not both. An example of the proposition is: Kathmandu is the capital of Nepal. This statement can be declared as true or false, so it is a proposition. Let us take another statement: What are you doing? This statement is not a proposition as it cannot be answered as a yes or a no. Truth function is a function to check whether a given statement or expression is true or false.

Propositional Logic
Logic is a set of approach with specific reasoning. The logic that deals with propositions is called a propositional logic. Some connectives that are used for compound proposition are given below:

Negation (¬ or ¯)

Let ‘p’ be a proposition, then the negation of ‘p’ is ‘not p’ or ‘it is not the case of p’ and denoted by ¬p. Its truth table is:

 p ¬p T F F T

Conjunction (
)

Let ‘p’ and ‘q’ be two propositions, then the conjunction of p and q is ‘p and q’ and is denoted by ‘p∧q’. Its truth table is:

 p q p∧q T T T T F F F T F F F F

Disjunction (∨)

Let ‘p’ and ‘q’ be two propositions, then the disjunction of p and q is ‘p or q’ and is denoted by ‘p∨q’. Its truth table is:

 p q p∨q T T T T F T F T T F F F

Implication (
→)

Let ‘p’ and ‘q’ be two propositions, then the implication of p and q is ‘If p then q’ or ‘p implies q’ and is denoted by ‘p → q’. Here, ’p’ is the hypothesis and ‘q’ is the conclusion. Its truth table is:

 p q p → q T T T T F F F T T F F T

Double Implication (
)

Let ‘p’ and ‘q’ be two propositions, then the double implication of p and q is ‘p if and only if q’ and is denoted by ‘p ↔ q’. Its truth table is:

 p q p ↔ q T T T T F F F T F F F T

Converse, Inverse and Contrapositive

Let ‘p’ and ‘q’ be two propositions. Then, the converse of ‘p → q’ is ‘q → p’. The inverse of ‘p → q’ is ‘¬p → ¬q’ and the contrapositive of ‘p → q’ is ‘¬q → ¬p’.

Tautology
Tautology is a compound statement which is always true no matter what the truth values of the constituent propositions is. For example, (p ∨ ¬p) is a tautology as shown in the truth table below:

 p ¬p P ∨ ¬p T F T F T T

Contradiction is a compound statement which is always false no matter what the truth value of constituent propositions is. For example, (p ∧¬p) is a contradiction as shown in the truth table below:

 p ¬p P ∧ ¬p T F F F T F

Contingency

Contingency is a compound statement which is either true or false no matter what the truth value of constituent propositions is.

Logical Equivalence
Let ‘p’ and ‘q’ be two compound propositions. Then, ‘p’ is logical equivalence to ‘q’ if the truth values of ‘p’ and ‘q’ are equal. If the truth values of p is equal to the truth values of q, then (p ↔ q) possess a tautology. For example, the implication of two compound propositions ‘p’ and ‘q’ is logically equivalent to its contrapositive which is shown in the truth table below:

 p q p → q ¬q ¬p ¬q → ¬p T T T F F T T F F T F F F T T F T T F F T T T T

Expressing Statements in Propositional Logic
To express a statement in propositional logic, we first analyse the given sentence and then divide the sentence into the different statements. We denote each statement with some alphabet and based on the given sentence, we prepare a propositional logic by connecting the statements using the appropriate connectives.

Few examples are given below:

If it is not snowing and I have time then I will go to beach.

Solution:

p: It is snowing.

q: I have time.

r: I will go to beach.

Now, the propositional logic is: (¬p ∧ q) → r

If Berries are ripe along the trial, hiking is safe if and only if grizzy bear are not seen in the area.

Solution:

p: Berries are ripe along the trial.

q: Hiking is safe.

r: Grizzy bear are not seen in the area.

The propositional logic is: (p → q) ↔ ¬r