Proof and Syntax

Flashcards covering core concepts, logical equivalence laws, formal proofs, and syntax rules from Lecture 2: Proof and Syntax.

Proposition

A statement that expresses a fact or opinion and can be assigned a truth value given a suitable definition.

Liar's Paradox

A self-referential and contradictory statement (such as 'This statement is false') that cannot have a truth value and lacks meaning.

Tautology

A statement that is always true in any context, represented in formal logic by the symbol $\top$ (verum or top).

Contradiction

A statement that cannot be true, represented in formal logic by the symbol $\bot$ (falsum or bottom).

Contingency

A logical statement that is neither a tautology nor a contradiction.

Double Negation Law (DN)

A logical law stating that negating a proposition twice returns the original truth value: $\neg(\neg P) \equiv P$.

Law of Tautology (LT)

A logical law stating that every proposition is either true or false: $P \vee \neg P \equiv \top$.

Law of Contradiction (LC)

A logical law stating that no proposition can be both true and false: $P \wedge \neg P \equiv \bot$.

Negated Constants Law (Neg)

A logical law stating that tautologies and contradictions are opposites: $\neg\top \equiv \bot$ and $\neg\bot \equiv \top$.

Idempotent Law (Id)

A logical law stating that conjunction or disjunction of a proposition with itself is unchanged: $P \wedge P \equiv P$ and $P \vee P \equiv P$.

Zero and Unit Law for Conjunction

A law stating that $\bot$ is the zero element of conjunction ($P \wedge \bot \equiv \bot$) and $\top$ is the identity element ($P \wedge \top \equiv P$).

Commutative Law (Comm)

A logical law stating that changing the order of operands does not affect the truth value: $(P \vee Q) \equiv (Q \vee P)$.

Associative Law (Assoc)

A logical law stating that grouping of operands does not affect the truth value: $(P \vee Q) \vee R \equiv P \vee (Q \vee R)$.

Identity and Zero Law for Disjunction

A law stating that $\bot$ is the identity element of disjunction ($P \vee \bot \equiv P$) and $\top$ is the zero element ($P \vee \top \equiv \top$).

Distributivity Laws

Logical equivalences showing that conjunction distributes over disjunction ($P \wedge (Q \vee R) \equiv (P \wedge Q) \vee (P \wedge R)$) and disjunction distributes over conjunction ($P \vee (Q \wedge R) \equiv (P \vee Q) \wedge (P \vee R)$).

De Morgan's Law for And (DeM)

A logical law stating that the negation of a conjunction is the disjunction of negations: $\neg(P \wedge Q) \equiv (\neg P \vee \neg Q)$.

De Morgan's Law for Or (DeM)

A logical law stating that the negation of a disjunction is the conjunction of negations: $\neg(P \vee Q) \equiv (\neg P \wedge \neg Q)$.

Augustus De Morgan

A mathematician (1806–1871) associated with De Morgan's Laws in symbolic logic.

Material Conditional Identity (Cond)

A logical law stating that a conditional statement $P \rightarrow Q$ is true when the antecedent is false or the consequent is true: $P \rightarrow Q \equiv (\neg P \vee Q)$.

Carnap

The logic system used to check and verify formal proofs.

QED Symbol ($\square$)

A square symbol placed at the end of a formal proof meaning 'quod erat demonstrandum' (it has been proved).

Formal Syntax

Rules that use symbols to build sentences or formulae where variables and operators must be given in the correct order.

Well-formed Formula (wff)

A syntactically valid formula constructed according to formal syntax rules in logic.

Backus-Naur Form (BNF)

A notation used to specify syntax concisely using non-terminal symbols, terminal symbols, and pipe symbols ($|$) to separate alternative forms.

Biconditional ($\leftrightarrow$)

A logical connective defined as $P \leftrightarrow Q \equiv (P \rightarrow Q) \wedge (Q \rightarrow P)$.

Operator Precedence in Propositional Logic

The standard parsing hierarchy for logical connectives: $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$.

Right-associative Operator

A property of binary logical connectives where unbracketed expressions group their right-hand arguments first (e.g., $P \rightarrow Q \rightarrow R \equiv P \rightarrow (Q \rightarrow R)$).

Parse Tree

A visual representation of the syntactic structure of a formula, where branch nodes represent operators/connectives and leaf nodes represent terminal symbols.