Proposition

A proposition is a declarative statement which is either true or false. For example, considering the statement: New Delhi is the capital of India, is a proposition. On the other hand, considering: $x+2=10$, is not a proposition because the value of $x$ is unknown, therefore, cannot be stated whether, it is true or false.

---

Propositional Operators

Negation

Representation: $\sim,\lnot$

If $p$ is the proposition, then the negation of $p$ is denoted by $\sim p$, and it simply reverses the truth value of $p$.

E.g.:

$p:\textnormal{It is cold today}$

$\sim p:\textnormal{It is not cold today}$

Truth table:

$p$	$\sim p$
T	F
F	T

Conjugation

Representation: $\wedge$

For any two proposition, $p$ and $q$, the conjunction is denoted by $p\wedge q$, and it gives the true value when both $p$ and $q$ are true.

E.g.:

$p:\textnormal{It is cold today}$

$q:\textnormal{It is Friday}$

$p\wedge q:\textnormal{It is cold today and it is Friday}$

Truth table:

$p$	$q$	$p\wedge q$
T	T	T
T	F	F
F	T	F
F	F	F

Disjunction

Representation: $\vee$

For any two proposition $p$, and $q$, the disjunction is denoted by $p\vee q$, and gives the true value if either of them or both are true.

E.g.:

$p:\textnormal{It is cold today}$

$q:\textnormal{It is Friday}$

$p\vee q:\textnormal{Either it is cold today or it is Friday}$

Truth table:

$p$	$q$	$p\vee q$
T	T	T
T	F	T
F	T	T
F	F	F

Implication

Representation: $\to$

For any two proposition $p$ and $q$, the statement if $p$ then $q$ is called an implication and it is denoted by $p\to q$. It gives false when $p$ is true and $q$ is false, otherwise it is true.

E.g.:

$p:\textnormal{It is cold today}$

$q:\textnormal{It is Friday}$

$p\to q:\textnormal{If it is cold today then it is Friday}$

Truth table

$p$	$q$	$p\to q$
T	T	T
T	F	F
F	T	T
F	F	T

Bi

Representation: $\leftrightarrow$

For any two proposition $p$ and $q$, the statement $p$, iff., $q$ is called biconditional, and is denoted by $p\leftrightarrow q$. It gives true value when both $p$ and $q$ have the same value.

E.g.:

$q:\textnormal{It is cold today}$

$q:\textnormal{It is Friday}$

$p\leftrightarrow q:\textnormal{It is cold today iff. it is Friday}$

Truth table

$p$	$q$	$p\leftrightarrow q$
T	T	T
T	F	F
F	T	F
F	F	T

---

Example 1: Express the following statement in propositional logic:

$$\textnormal{It is Saturday and I am not going to college}$$

Solution:

$p:\textnormal{It is Saturday}$

$q:\textnormal{I am going to college}$

Well formed formula (WFF): $p\wedge\sim q$

Example 2: Express the following statement in propositional logic:

$$\textnormal{Either it is hot today or I am at home}$$

Solution:

$p:\textnormal{It is hot today}$

$q:\textnormal{I am at home}$

Well formed formula (WFF): $p\vee q$

Example 3: Express the following statement in propositional logic:

$$3+4\ne6\textnormal{ and C.S. class will not be held}$$

Solution:

$p:3+4=6$

$q:\textnormal{C.S. class will be held}$

Well formed formula (WFF): $\sim p\wedge\sim q$

Example 4: Draw the truth table for $(\sim p\wedge q)\wedge \sim r$.

$p$	$q$	$r$	$\sim p\wedge q$	$(\sim p\wedge q)\wedge \sim r)$
T	T	T	F	F
T	T	F	F	F
T	F	T	F	F
T	F	F	F	F
F	T	T	T	F
F	T	F	T	T
F	F	T	F	F
F	F	F	F	F

Example 5: Check the equivalence for the following:

$$p\to(q\to r)\cong(p\wedge q)\to r$$

Solution:

$p$	$q$	$r$	$q\to r$	$p\to(q\to r)$	$p\wedge q$	$(p\wedge q)\to r$
T	T	T	T	T	T	T
T	T	F	F	F	T	F
T	F	T	T	T	F	T
T	F	F	T	T	F	T
F	T	T	T	T	F	T
F	T	F	F	T	F	T
F	F	T	T	T	F	T
F	F	F	T	T	F	T

From the truth table, it can be concluded that:

$$p\to(q\to r)\cong(p\wedge q)\to r$$

Implication and bicondition can be further be simplifed as:

$$p\rightarrow q=\sim p\vee q$$ $$p\leftrightarrow q=(p\rightarrow q)\wedge(q\rightarrow p)=(\sim p\vee q)\wedge(\sim q\vee p)$$

---

Laws for propositional logic

Following are the laws for propositional logic:

1. Idempotent law:
   • $p\wedge p=p$
   • $p\vee p=p$
2. Commutative law:
   • $p\vee q=q\vee p$
   • $p\wedge q=q\wedge p$
3. Associative law:
   • $(p\vee q)\vee r=p\vee(q\vee r)$
   • $(p\wedge q)\wedge r=p\wedge(q\wedge r)$
4. Distributive law:
   • $p\wedge(q\vee r)=(p\wedge q)\vee(p\wedge r)$
   • $p\vee(q\wedge r)=(p\vee q)\wedge(p\vee r)$
5. Identity law:
   • $p\vee T=T$
   • $p\wedge T=p$
   • $p\vee F=p$
   • $p\wedge F=F$
6. De-morgan's law:
   • $\sim(p\vee q)=\sim p\wedge\sim q$
   • $\sim(p\wedge q)=\sim p\vee\sim q$
7. Involution law:
   • $\sim(\sim p)=p$
8. Compliment law:
   • $p\vee\sim p=T$
   • $p\wedge\sim p=F$
9. Contrapositive law:
   • $p\rightarrow q=\sim q\rightarrow\sim p$

---

Conditions for compound statements

Tautology

We define a term, tautology for a compound statement such that its truth value is always true for all possible combinations. For example:

$$(p\wedge q)\rightarrow(p\vee q)$$

Truth table:

p	q	$p\wedge q$	$p\vee q$	$(p\wedge q)\rightarrow(p\vee q)$
T	T	T	T	T
T	F	F	T	T
F	T	F	T	T
F	F	F	F	T

Since, all values for the compound statemnet is true, it is tautogenic.

Contradiction

We define a term, contradiction for a compound statement such that its truth value is always false for all possible combinations. For example:

$$\sim(\sim(p\wedge q)\leftrightarrow(\sim p\vee\sim q))\\ =\sim((\sim(p\wedge q)\rightarrow(\sim p\vee\sim q))\wedge((\sim p\vee\sim q)\rightarrow(\sim(p\wedge q)))\\$$

We know, as per De-morgan's theorem: $\sim p\vee\sim q=\sim(p\wedge q)$

$$\therefore \sim((\sim(p\wedge q)\rightarrow(\sim p\vee\sim q))\wedge((\sim p\vee\sim q)\rightarrow\sim(p\wedge q)))\\ =\sim((\sim(p\wedge q)\rightarrow\sim(p\wedge q))\wedge(\sim(p\wedge q)\rightarrow\sim(p\wedge q)))\\$$

We know: $p\rightarrow p=T$. Similarly, $\sim(p\wedge q)\rightarrow\sim(p\wedge q)=T$

$$\therefore \sim((\sim(p\wedge q)\rightarrow\sim(p\wedge q))\wedge(\sim(p\wedge q)\rightarrow\sim(p\wedge q)))\\ =\sim(T\wedge T)=\sim T=F$$

Since the final result is $F$, therefore the compound statement is contradictive.

Contigency

A compound statement that is neither a tortology nor a contradiction is called contigency. For example: $p\vee q$

Example 6: $\sim p\rightarrow \sim q\cong \sim q\vee p$. Prove the equivalence.

$$\textnormal{LHP}\\ =\sim p\rightarrow\sim q\\ =\sim(\sim p)\vee \sim q$$

As: $p\to q=\sim p\vee q$, and since $\sim(\sim p)=p$

$$\therefore \sim(\sim p)\vee \sim q\\ =p\vee\sim q=\sim q\vee p=\textnormal{RHP}$$

Therefore, $\sim p\rightarrow \sim q\cong \sim q\vee p$.

Example 7: Show that $(p\wedge q)\to(p\vee q)$ is tautogenic.

$$(p\wedge q)\to(p\vee q)\\ =\sim(p\wedge q)\vee p\vee q\\ =\sim p \vee \sim q\vee p \vee q\\ =(\sim p\vee p)\vee(\sim q\vee q)\\ =T\vee T=T=\textnormal{RHP}$$

Therefore, the given proposition is tautogenic

Example 8: Show that $p\to(p\wedge(q\to p))$ is tautogenic.

$$p\to(p\wedge(q\to p))\\ =p\to(p\wedge(\sim q\vee p))\\ =\sim p\vee(p\wedge(\sim q\vee p))\\ =(\sim p\vee p)\wedge(\sim p\vee \sim q \vee p)\\ =T\wedge(T\vee\sim q)\\ =T\wedge T=T$$

Therefore, the given proposition is tautogenic.

Problem 1: Prove the equivalence of $p\to(q\to r)\cong(p\wedge q)\to r$.