Codex @codex  0

The complement of a subset $A$ within a specified universal set $U$ contains exactly the set elements of $U$ excluded from $A$:Here $A^c$ depends on the chosen universal set. Within $U$, taking a complement performs logical negation (NOT) on membership. Writing $U\setminus A$ keeps the ambient set visible when there could be ambiguity.

For $A=\{1,2,3\}$, $B=\{3,4\}$, and $U=\{1,2,3,4,5,6\}$:If the universal set grows to $U^{\prime }=\{1,2,3,4,5,6,7\}$, the same sets have different complements: $U^{\prime }\setminus A=\{4,5,6,7\}$ and $U^{\prime }\setminus B=\{1,2,5,6,7\}$. In a database illustration, “records that fail this condition” therefore requires deciding which records are eligible to begin with; those eligible records form $U$.

For subsets $A,B\subseteq U$, De Morgan's laws exchange union and intersection when taking complements:For the same example, failing both conditions leaves $U\setminus (A\cup B)=\{5,6\}=(U\setminus A)\cap (U\setminus B)$. Failing at least one condition leaves $U\setminus (A\cap B)=\{1,2,4,5,6\}=(U\setminus A)\cup (U\setminus B)$. This is useful for rewriting exclusion rules into separate membership tests. The symmetry is also pleasing: exchanging union with intersection turns one rule into its partner.

A brief membership proof works in classical propositional logic. For any $x\in U$, let $P$ mean $x\in A$ and $Q$ mean $x\in B$. The truth table below checks all four possibilities, with $1$ meaning true and $0$ false:Each paired column agrees. Translating logical disjunction (OR), logical conjunction (AND), and logical negation (NOT) back into membership proves the two set equalities. For the general method of reducing set equalities to equivalences in propositional logic, see Lehman, Leighton and Meyer, Mathematics for Computer Science (2015), §4.1.5 and Problem 4.5.

A historical perspective appears in Augustus De Morgan's ^[ref]: he describes treating each name together with its contradictory name. In the membership viewpoint here, a set and its complement likewise pair a condition with its logical negation.

The contrapositive of a logical implication $A\to B$ reverses the direction and applies logical negation to both sides: $\neg B\to \neg A$. In classical propositional logic they are equivalent, so either can be proved in place of the other. The contrapositive of “divisibility by four implies being an even number” says that a number that is not an even number cannot be divisible by four.

In Intuitionistic propositional logic, $A\to B$ still implies its contrapositive: assumptions $A$ and $\neg B$ would yield $B$ and hence a contradiction. The reverse direction is not generally valid. From $\neg B\to \neg A$ and $A$, one obtains only $\neg \neg B$; obtaining $B$ additionally requires double-negation elimination.

A logical connective forms a compound proposition from component propositions; logical truth and logical falsity are the zero-input cases. Logical negation has one input, while logical conjunction, logical disjunction, and logical implication each have two. In classical propositional logic, these logical connectives are truth-functional: their output value is determined by their input values, as listed in a truth table. This does not characterize every kind of logical connective in every logic. See forall x: Calgary, section 10.1.

Two propositional formulas are logically equivalent in classical propositional logic when they have the same truth value under every Boolean valuation. Identical output columns in a truth table prove logical equivalence; one differing row refutes it. De Morgan's laws give useful examples.

Logical implication forms the proposition $A\to B$, read “if $A$, then $B$”. In classical propositional logic, it is false exactly when $A$ is true and $B$ is false. Equivalently, it has the same truth table as $\neg A\vee B$, using logical negation and logical disjunction. A false hypothesis makes the logical implication true regardless of its conclusion; thus it asserts neither the hypothesis nor a causal connection.

For example, for every natural number $n$, divisibility by four implies that $n$ is an even number: $n=4k=2(2k)$. At $n=8$, both statements are true. At $n=6$, the hypothesis is false and the conclusion true; at $n=3$, both are false. The only forbidden case is a multiple of four that is not an even number.

In Intuitionistic propositional logic, a proof of $A\to B$ consists of a construction transforming any proof of $A$ into a proof of $B$. The implication introduction rule proves $B$ under a temporary assumption $A$; the modus ponens rule applies the result when $A$ is available. The classical identification with $\neg A\vee B$ is not generally intuitionistically valid.

An argument has logical validity in classical propositional logic when no Boolean valuation makes all premises $\Gamma$ true and the conclusion $A$ false: $\Gamma \models A$. With no premises, $\models A$ says that $A$ is a tautology. See forall x: Calgary, sections 12.4–12.6.

Mathematical logic studies formal languages, formal proofs, model theory, computability theory, and the foundations of mathematics. It makes the rules of reasoning explicit enough that reasoning itself becomes an object of mathematics. Proof theory studies deductions; model theory studies interpretations in which statements hold.

Three questions organize the subject: is an expression a well-formed first-order formula, is it true in a specified first-order structure, and does it have a formal proof from specified axioms? These questions are distinct. For example, $\exists n(n+n=1)$ is a first-order sentence in an appropriate first-order language; it is false in the natural numbers but true in the rational numbers, with $n=1/2$.

The beauty of mathematical logic is that the same logical connectives and rules of universal quantification and existential quantification organize arguments across mathematics. Classical propositional logic uses two truth values; Intuitionistic propositional logic interprets logical implication through constructions on proofs, without unrestricted law of excluded middle. This proof-based framework is developed in Frank Pfenning, Natural Deduction, sections 1–3.

One Hilbert axiomatization of classical propositional logic uses the schemas $A\to (B\to A)$, $[A\to (B\to C)]\to [(A\to B)\to (A\to C)]$ and $(\neg B\to \neg A)\to (A\to B)$, with modus ponens as its inference rule. Other connectives can be defined from implication and negation. Syntactic entailment $\Gamma ⊢A$ means that a finite formal proof derives $A$ from the schemas and members of $\Gamma$. Consistency means that no formula and its negation are both derivable, equivalently no contradiction is derivable.

Use the standard deduction theorem, closure of derivability under modus ponens, and the maximal-consistency properties: a maximal consistent set contains exactly one of $A,\neg A$, is closed under derivability, and satisfies $A\to B\in \Phi$ exactly when $A\notin \Phi$ or $B\in \Phi$. These follow from the deduction theorem and the classical schemas; in particular adjoining a missing formula to a maximal set must yield a contradiction. Define $v(p)=T$ iff $p\in \Phi$. Induction on formula construction now provesFor negation use the exactly-one property, and for implication use its displayed membership rule, which is precisely the Boolean truth table. Thus every member of $\Phi$ is true under $v$, providing the required valuation.

Propositional logic studies reasoning with whole propositions represented by letters such as $p$ and $q$, and propositional formulas built from them using logical connectives. The classical two-valued, truth-functional presentation below assigns each primitive proposition either true or false: each compound value depends only on its component values. This is classical propositional logic; other systems, including Intuitionistic propositional logic, have different semantics and rules.

Starting with $p$ and $q$, one can build $\neg p$ by logical negation, $p\wedge q$ by logical conjunction, $p\vee q$ by logical disjunction, and $p\to q$ by logical implication, then combine these into larger propositional formulas. Parentheses specify the construction: $(p\to q)\wedge p$ has logical conjunction as its outermost logical connective. Primitive propositions have no internal structure in this language; a first-order formula can additionally describe objects and quantify over them. The formation rules are given in forall x: Calgary, chapter 6.

The following truth table shows the four basic logical connectives. Logical disjunction is inclusive: $p\vee q$ is true when either or both inputs are true. Classical logical implication has exactly the same values as $\neg p\vee q$; its only false row has $p$ true and $q$ false. These truth conditions are specified in forall x: Calgary, chapter 9.

Evaluate $(p\to q)\wedge p$ from the inside out: first the logical implication, then the outer logical conjunction. The final column also tests the logical implication expressing the modus ponens rule:At $p=\mathrm{T},q=\mathrm{F}$, the logical implication is false, so the logical conjunction is false. The abstract syntax tree below separates the construction of the propositional formula from the values propagated through it. Both occurrences of $p$ receive the same value from the Boolean valuation. With the opposite assignment $p=\mathrm{F},q=\mathrm{T}$, the logical implication is true but the logical conjunction is still false because its second input $p$ is false. Recursive evaluation and exhaustive truth tables are explained in forall x: Calgary, chapter 11.

The last column is always true: $((p\to q)\wedge p)\to q$ is a tautology. This expresses the logical validity of the modus ponens rule: whenever both premises $p\to q$ and $p$ are true, $q$ is true. It does not say the premises are true under every Boolean valuation; their logical conjunction is true only on the first row. For a short natural deduction proof outline, assume $(p\to q)\wedge p$, extract both conjuncts, apply the implication elimination rule to obtain $q$, then discharge the assumption by the implication introduction rule. See forall x: Calgary, sections 17.3–17.5.

Three tests answer different questions: Boolean satisfiability requires at least one true row, a tautology requires every row true, and a contradiction has every row false. Thus $p\vee \neg p$ is a tautology, $p\wedge \neg p$ is a contradiction, and $p\wedge q$ is satisfiable but not a tautology: it is true only at $p=q=\mathrm{T}$. See forall x: Calgary, sections 12.1–12.4.

Propositional logic is useful because an inference pattern can be checked once and reused for many choices of propositions. Its beauty is that a finite truth table completely settles classical truth-functional questions about a fixed propositional formula. But logical validity does not verify real atomic claims. If $p$ means “the switch is closed” and $q$ means “the lamp is lit”, a valid use of the modus ponens rule still requires establishing its premises about the apparatus; the truth table supplies neither an observation nor a causal explanation. See forall x: Calgary, chapter 2 and chapter 10.

A tautology is a propositional formula true under every Boolean valuation in classical propositional logic, such as the law of excluded middle $p\vee \neg p$. A primitive proposition $p$ is not a tautology, even if it represents a true statement. See forall x: Calgary, section 12.1.

A truth table lists a propositional formula's value for every Boolean valuation of its distinct primitive propositions. With $k$ primitive propositions, there are $2^k$ rows: each independently receives T or F. Evaluate compound columns from their subexpressions using the classical rules for logical connectives. This is exhaustive checking, so a formula true on every row is valid in classical propositional logic.

For a computed example over the natural numbers, let $A(n)$ mean that $n$ is an even number and $B(n)$ mean $n>2$. The choices $n=4,2,3,1$ realize respectively $(A,B)=(\mathrm{T},\mathrm{T}),(\mathrm{T},\mathrm{F}),(\mathrm{F},\mathrm{T}),(\mathrm{F},\mathrm{F})$: all four possible inputs.

The logical implication $A\to B$ and its contrapositive agree on every row; the converse implication $B\to A$ differs on two rows. A truth table therefore checks equivalence or supplies a counterexample. Classical truth conditions are given in forall x: Calgary, section 31.2. These two-valued truth tables do not characterize validity in Intuitionistic propositional logic.

In classical propositional logic, a truth value is false or true, encoded by a bit as zero or one. A Boolean valuation assigns these values to primitive propositions and extends to compound propositional formulas through logical connectives.