The Foundations: Logic and Proofs

Proposition

A declarative sentence that is either true or false.

Propositional Variable

A symbol such as p, q, r, used to represent a proposition.

T

The proposition that is always true.

F

The proposition that is always false.

Compound Proposition

A statement constructed from logical connectives and other propositions.

Negation Symbol

¬ denotes the operation that reverses the truth value of a proposition.

Negation

The operation that takes a proposition p and forms ¬p, which is true when p is false and false when p is true.

Conjunction Symbol

∧ denotes the logical 'and' operation.

Conjunction

The operation that forms p ∧ q, which is true when both p and q are true, and false otherwise.

Disjunction Symbol

∨ denotes the logical 'or' operation.

Disjunction

The operation that forms p ∨ q, which is true if at least one of p or q is true, and false only if both are false.

Inclusive Or

A disjunction that is true if either or both propositions are true.

Exclusive Or Symbol

⊕ denotes the 'xor' operation.

Exclusive Or

An operation where p ⊕ q is true when exactly one of p or q is true, and false when both are true or both are false.

Implication Symbol

→ denotes the conditional 'if…then…' operation.

Implication

The conditional statement p → q is false only when p is true and q is false; true otherwise.

Hypothesis (Implication)

The antecedent or premise of a conditional statement p → q.

Conclusion (Implication)

The consequent or result in a conditional statement p → q.

Converse

The proposition q → p formed from p → q by interchanging antecedent and consequent.

Contrapositive

The proposition ¬q → ¬p formed from p → q by negating and swapping antecedent and consequent.

Inverse

The proposition ¬p → ¬q formed from p → q by negating both antecedent and consequent.

Biconditional Symbol

↔ denotes the 'if and only if' operation.

Biconditional

The statement p ↔ q is true when p and q share the same truth value, true or false.

Truth Table

A tabular method of representing truth values of propositions for all possible combinations of truth values of atomic propositions.

Logically Equivalent

Two compound propositions are logically equivalent if they always have the same truth value.

Equivalence Symbol

⇔ or ≡ expresses that two propositions are logically equivalent.

Precedence of Logical Operators

Ordering of logical operations: 1) ¬, 2) ∧, 3) ∨, 4) →, 5) ↔.

System Specification

A list of propositions describing system requirements using logic.

Consistent Specifications

A set of propositions is consistent if truth values can be assigned to make all true.

Knight (Logic Puzzle)

An inhabitant who always tells the truth.

Knave (Logic Puzzle)

An inhabitant who always lies.

Logic Circuit

An electronic circuit where signals correspond to truth values; 0 stands for false and 1 stands for true.

Inverter (NOT Gate)

A gate that outputs the negation of its input bit.

OR Gate

A gate that outputs true if at least one input bit is true.

AND Gate

A gate that outputs true only if both input bits are true.

Tautology

A proposition that is always true, regardless of the truth values of its components.

Contradiction

A proposition that is always false, regardless of the truth values of its components.

Contingency

A proposition that is sometimes true and sometimes false, depending on the truth values of its components.

De Morgan's Laws

Rules relating conjunctions and disjunctions through negation: ¬(p ∨ q) ≡ (¬p ∧ ¬q), ¬(p ∧ q) ≡ (¬p ∨ ¬q).

Identity Laws

Logical laws stating p ∧ T ≡ p and p ∨ F ≡ p.

Domination Laws

Logical laws stating p ∨ T ≡ T and p ∧ F ≡ F.

Idempotent Laws

Logical laws stating p ∨ p ≡ p and p ∧ p ≡ p.

Double Negation Law

Logical law stating ¬(¬p) ≡ p.

Negation Laws

Logical laws such as p ∨ ¬p ≡ T and p ∧ ¬p ≡ F.

Commutative Laws

Logical laws such as p ∨ q ≡ q ∨ p and p ∧ q ≡ q ∧ p.

Associative Laws

Logical laws such as (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) and (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).

Distributive Laws

Logical laws such as p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).

Absorption Laws

Logical laws expressing relationships like p ∨ (p ∧ q) ≡ p and p ∧ (p ∨ q) ≡ p.