## Propositional Logic

**Logic** is a formal method of reasoning.

A **proposition** is an elementary atomic sentence that may either be true or false but may take no other value.

A **simple proposition** is one that does not contain any other proposition as a part.

A **compound proposition** is one with two or more simple propositions as parts.

An **operator** or **connective** joins simple propositions into compounds.

Following are the various types of connectives:

**Disjunctive (OR)**: It means at least one of the two arguments is true. OR is represented by + or ∨.**Conjunctive (AND)**: It means that both the arguments are true. AND is represented by . or & or ∧.**Conditional (Implication or If Then)**: It means that if one argument is true then other argument is true. Implication is represented by ⇒ or → or ⊃.**Bi-conditional (Equivalence or If And Only If):**It means that either both arguments are true or both are false. Equivalence is represented by ⇔ or ≡.**Negation (NOT):**Actually, it is an operator, and not a connective. It means that an argument is false. NOT is represented by ∼ or ‘ or ‾.

Propositions are also called as sentences or statements or formula or **well-formed formula**.

**Truth value** is defined as truth or falsity of a proposition.

A **truth table** is a complete list of all possible truth values of a proposition.

### Truth Table for NOT

p | ~p |
---|---|

0 | 1 |

1 | 0 |

### Truth Table for OR

p | q | p + q |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

### Truth Table for AND

p | q | p . q |
---|---|---|

0 | 0 | 0 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

### Truth Table for Implication

p | q | p ⇒ q |
---|---|---|

0 | 0 | 1 |

0 | 1 | 1 |

1 | 0 | 0 |

1 | 1 | 1 |

### Truth Table for Equivalence

p | q | p ⇔ q |
---|---|---|

0 | 0 | 1 |

0 | 1 | 0 |

1 | 0 | 0 |

1 | 1 | 1 |

### Some Related Terms

**Contingencies** are the propositions that have some combination of 1s and 0s in their truth table column.

**Tautologies** are the propositions having nothing but 1s in their truth table column.

**Contradictions** are the propositions having nothing but 0s in their truth table column.

Two statements are **consistent** if and only if their conjunction is not a contradiction.

**Converse** of p ⇒ q is q ⇒ p.

**Inverse** of p ⇒ q is p’ ⇒ q’.

**Contrapositive** of p ⇒ q is q’ ⇒ p’.

The logical process of drawing conclusions from given propositions is called **syllogism**.

The propositions used to draw conclusion are called **premises**.

**Modus Ponens** is

p p ⇒ q ------ q

**Chain rule** is

p ⇒ q q ⇒ r ------ p ⇒ r

### Equivalence Laws

**Properties of 0**

0 + p = p

0 . p = 0

**Properties of 1**

1 + p = 1

1 . p = p

**Absorption Law**

p + pq = p

p + (p + q) = p

**Involution**

~(~p) = p

**Idempotence Law**

p + p = p

p . p = p

**Complementarity Law**

p + ~p = 1

p . ~p = 0

**Commutative Law**

p + q = q + p

p . q = q . p

**Associative Law**

(p + q) + r = p + (q + r)

(p . q) . r = p . (q . r)

**Distributive Law**

p . (q + r) = (p . q) + (p . r)

p + (q . r) = (p + q) . (p + r)

p + ~pq = p + q

**De Morgan’s Law**

~(p + q) = ~p . ~q

~(p . q) = ~p + ~q

**Conditional Elimination**

p ⇒ q = ~p + q

**Bi-conditional Elimination**

p ⇔ q = (p ⇒ q) . (q ⇒ p)

**Transposition**

p ⇒ q = ~q ⇒ ~p

## Logic Gates

A **gate** is an electronic circuit which operates on one or more signals to produce an output signal.

The three **basic logic gates** are:

- NOT gate (inverter)
- OR gate
- AND gate

An **Inverter (NOT gate)** is a gate with only one input signal and one output signal. The output state is always the opposite of the input state.

The **OR gate** has two or more input signals but only one output signal. If any one of the input signals is 1, the output signal is 1, otherwise the output is 0.

The **AND gate** two or more input signals but produce only one output signal. When all inputs are 1, then the output is one, otherwise the output is 0.

### More Logic Gates

The **NOR gate** has two or more input signals but only one output signal. If all the inputs are 0s, then the output is 1, otherwise the output is 0.

The **NAND gate** has two or more input signals but only one output signal. If all the inputs are 1, then the output is 0, otherwise the output is 1.

The **XOR (Exclusive OR) gate** has two or more input signals but only one output signal. It produces output 1 for only those input combinations that have odd number of 1s.

The **XNOR (Exclusive NOR)** gate has two or more input signals but only one output signal. It produces output 1 when the input combination has even number of 1s.

NAND and NOR gates are known as **universal gates** because we can easily implement other switching functions (AND, OR, NOT) using these gates.