📖

Unit 1 -- Mathematical Logic

Reference book

DAY 1

21-02-2024

Propositions and Truth Table

A proposition is a declarative sentence (i.e., a sentence that declares a fact) that is either true or false, but not both.

Example:
1. Washington, D.C., is the capital of USA
2. Toronto is the capital of CANADA
3. 1+1=2
4. 2+2=3

Propositions 1 and 3 are true, whereas 2 and 4 are false.

Truth Table

Truth table is the representation of all the True and False values a statement has.

Example: Proposition $p$ can have either True or False values at one time

Note: Number of Truth value of a table can be determined by $2^{n}\text{ where n = Number of proposition}$

Negation ($\lnot$/not/~/!)

Let $p$ be a proposition. The negation of $p$, denoted by $\lnot p$, is the inverse of the original proposition/statement.

Conjunction ($\land$/and/but)

Let $p$ and $q$ be propositions. The conjunction of $p$ and $q$, denoted by $p \land q$, is the proposition “$p$ and $q$”. The conjunction $p \land q$ is true when both p and q are true and false otherwise.

Disjunction ($\lor$/or)

Let $p$ and $q$ be propositions. The disjunction of $p$ and $q$, denoted by $p \lor q$, is the proposition “$p$ or $q$”. The conjunction $p \lor q$ is false when both p and q are false and true otherwise.

Conditional Statements

Let $p$ and $q$ be propositions. The conditional statement $p \rightarrow q$ is the proposition “if $p$, then $q$.” The conditional statement $p \rightarrow q$ is false when $p$ is true and $q$ is false, and true otherwise. In the conditional statement $p \rightarrow q$, $p$ is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).

Bi-Conditional Statements

Let $p$ and $q$ be propositions. The biconditional statement $p \leftrightarrow q$ is the proposition “$p$ if and only if $q$.” The biconditional statement $p \leftrightarrow q$ is true when $p$ and $q$ have the same truth values, and is false otherwise. Biconditional statements are also called bi-implications.

Truth table for all of the above statements

$p$$q$$\lnot\ p$$p\land q$$p\lor q$$p \rightarrow q$$p \leftrightarrow q$
$T$$T$$ F $$ T $$ T $$ T $$ T $
$T$$F$$ F $$ F $$ T $$ F $$ F $
$F$$T$$ T $$ F $$ T $$ T $$ F $
$F$$F$$ T $$ F $$ F $$ T $$ T $

Cheatsheet

ConnectiveSymbolStatement
and$\land$Conjunction
or$\lor$Disjunction
not~,$\lnot$Negation
if…then$\rightarrow, \Rightarrow$Conditional
if and only if$\leftrightarrow, \Leftrightarrow$Bi-conditional

DAY 2

28-02-2024

Tautologies, Contradictions and Contingency

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, 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.

Example:

$p$$\lnot\ p$$p\lor\lnot\ p$$p\land\lnot\ p$
$T$$F$$T$$F$
$F$$T$$T$$F$

Logical Equivalence

Compound propositions that have the same truth values in all possible cases are called logically equivalent. We can also define this notion as follows.

The compound propositions $p$ and $q$ are called logically equivalent if $p \Leftrightarrow q$ is a tautology. The notation $p \equiv q$ denotes that $p$ and $q$ are logically equivalent.

Note: The symbol $\equiv$ is not a logical connective, and $p \equiv q$ is not a compound proposition but rather is the statement that $p \leftrightarrow q$ is a tautology. The symbol $\Leftrightarrow$ is sometimes used instead of $\equiv$ to denote logical equivalence.

Laws of Proposition

Commutative Laws

  1. $p\lor q \equiv p \land q$
  2. $p\land q \equiv p \lor q$

Associative Laws

  1. $p\lor (q\lor r) \equiv (p\lor q)\lor r$
  2. $p\land (q\land r) \equiv (p\land q)\land r$

Distributive Laws

  1. $p\lor (q\land r) \equiv (p\lor q)\land (p\lor r)$
  2. $p\land (q\lor r) \equiv (p\land q)\lor (p\land r)$

De Morgan’s Laws

  1. $\lnot\ (p\lor q) \equiv \lnot\ p \land \lnot\ q$
  2. $\lnot\ (p\land q) \equiv \lnot\ p \lor \lnot\ q$

Double Negation Laws

  1. $\lnot\ (\lnot\ p) \equiv p$

Identity Laws

  1. $p\land T \equiv p$
  2. $p\lor F \equiv p$

Domination Laws

  1. $p\lor T \equiv T$
  2. $p\land F \equiv F$

Negation Laws

  1. $p\lor \lnot\ p\equiv T$
  2. $p\land \lnot\ p\equiv F$

Idempotent Laws

  1. $p\lor p \equiv p$
  2. $p\land q\equiv p$

Absorption Laws

  1. $p\lor (p\land q) \equiv p$
  2. $p\land (p\lor q) \equiv p$

Logical equivalence using conditional preposition

  1. $p\rightarrow q \equiv \lnot\ p \lor q$
  2. $p\rightarrow q \equiv \lnot\ q \rightarrow\lnot\ q$
  3. $p\lor q \equiv \lnot\ p \rightarrow q$
  4. $p\land q \equiv \lnot\ (p \rightarrow\lnot\ q)$
  5. $\lnot\ (p\rightarrow q) \equiv p \land\lnot\ q$
  6. $(p\rightarrow q) \land (p\rightarrow r) \equiv p \rightarrow (q\land r)$

🄯 Copyleft 2022-2023 B4UC. No rights reserved