Propositions

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

We use letters, or other symbols, to denote propositional variables (or sentential variables), that is, variables that represent propositions, just as letters are used to denote numerical variables.

The conventional letters used for propositional variables are p, q, r, s, ... . The truth value of a proposition true, denoted by True ( or T or 1), if it is a true proposition, and the truth value of a proposition is false, denoted by False, F (or 0), if it is a false proposition. Propositions that cannot be expressed in terms of simpler propositions are called atomic propositions.

The area of logic that deals with propositions is called the propositional logic.

It was first developed systematically by the Greek philosopher Aristotle more than 2300 years ago.

Negation

Let $p$ be a proposition.

The negation of p, denoted by ¬p (also denoted by p̅ or p̚), is the statement “It is not the case that p.”.

The proposition ¬p is read “not p.” The truth value of the negation of p, ¬p, is the opposite of the truth value of p.

not False = True;
not True = False;

¬0 = 1
¬1 = 0

Other notations you might see are ¬p, p̚, p̅, ∼p, −p, p′, Np, and !p.

The Truth Table for the Negation of a Proposition.

p	¬p
0	1
1	0

And & Or

The conjunction of p and q, denoted by p ∧ q, is the proposition “p and q.” The conjunction p ∧ q is true when both p and q are true and is false otherwise.

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

p	q	p∧q
0	0	0
0	1	0
1	0	0
1	1	1

p	q	p∨q
0	0	0
0	1	1
1	0	1
1	1	1

Let p and q be propositions. The exclusive or of p and q, denoted by p ⊕ q (or p XOR q, or p⊻q), is the proposition that is true when exactly one of p and q is true and is false otherwise

p	q	p⊻q
0	0	0
0	1	1
1	0	1
1	1	0

If

Let p and q be propositions. The conditional statement p → q is the proposition “if p, then q.” The conditional statement p → q is false when p is true and q is false, and true otherwise.

In the conditional statement p → q, p is called the hypothesis (or antecedent or premise) and q is called the conclusion (or consequence).

p	q	p→q
0	0	1
0	1	1
1	0	0
1	1	1

“if p, then q”
“if p, q”
“p is sufficient for q”
“q if p”
“q when p”
“a necessary condition for p is q” “q unless ¬p” “p implies q”
“p only if q”
“a sufficient condition for q is p” “q whenever p”
“q is necessary for p”
“q follows from p”
“q provided that p”

Converse

of p → q
Is the proposition q → p

Contrapositive

of p → q
Is the proposition ¬q → ¬p

Inverse

The proposition ¬p → ¬q is called the inverse

Biconditional

The Truth Table for the Biconditional p ↔ q.

p	q	p↔q
0	0	1
0	1	0
1	0	0
1	1	1

“p is necessary and sufficient for q” “if p then q, and conversely”
“p iff q.” “p exactly when q.”

Logic Systems

System specifications should be consistent, that is, they should not contain conflicting propositions.

Propositional logic can be applied to the design of computer hardware. This was first observed in 1938 by Claude Shannon in his MIT master’s thesis.

p 
┗━o▷ ¬p

p q  D
┃ ┗━╭─╮
┃   │∧╞ p∧q
┗━━━╰─╯

p q  ☽
┃ ┗━╭╌╮
┃   ┆∨╞ p∨q
┗━━━╰╌╯

Tautology

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.

Contradiction

A compound proposition that is always false is called a contradiction.

Contingency

A compound proposition that is neither a tautology nor a contradiction is called a contingency.

Equivalency

The compound propositions p and q are called logically equivalent if p ↔ q is a tautology. The notation p ≡ q denotes that p and q are logically equivalent.

The symbol ⇔ is sometimes used instead of ≡ to denote logical equivalence

De Morgan’s Laws.

¬(p ∧ q) ≡ ¬p ∨ ¬q 
¬(p ∨ q) ≡ ¬p ∧ ¬q 
``

# Logic Rules
```Ada
Equivalence		Name

p ∧ 1 ≡ p		Identity laws 
p ∨ 0 ≡ p

p ∨ 1 ≡ 1		Domination laws 
p ∧ 0 ≡ 0

p ∨ p ≡ p		Idempotent laws 
p ∧ p ≡ p

¬(¬p) ≡ p 		Double negation law

p ∨ q ≡ q ∨ p 		Commutative laws 
p ∧ q ≡ q ∧ p

(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)		Associative laws 
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)

p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)		Distributive laws 
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

¬(p ∧ q) ≡ ¬p ∨ ¬q 	De Morgan’s laws 
¬(p ∨ q) ≡ ¬p ∧ ¬q

p ∨ (p ∧ q) ≡ p 	Absorption laws 
p ∧ (p ∨ q) ≡ p

p ∨ ¬p ≡ 1		Negation laws 
p ∧ ¬p ≡ 0


Conditional equivalents
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p
p ∨ q ≡ ¬p → q
p ∧ q ≡ ¬(p → ¬q)
¬(p → q) ≡ p ∧ ¬q
(p → q) ∧ (p → r) ≡ p → (q ∧ r) 
(p → r) ∧ (q → r) ≡ (p ∨ q) → r 
(p → q) ∨ (p → r) ≡ p → (q ∨ r) 
(p → r) ∨ (q → r) ≡ (p ∧ q) → r 
(p → q) ∧ (q → r) ≡ p → r 


Biconditional  equivalents
p ↔ q ≡ (p → q) ∧ (q → p) 
p ↔ q ≡ ¬p ↔ ¬q
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q) 
¬(p ↔ q) ≡ p ↔ ¬q 

A compound proposition is satisfiable if there is an assignment of truth values to its variables that makes it true (that is, when it is a tautology or a contingency).

When no such assignments exists, that is, when the compound proposition is false for all assignments of truth values to its variables, the compound proposition is unsatisfiable.