Logic Reference

Propositional logic deals with propositions (statements that are true or false) connected by logical operators (AND, OR, NOT, implication). It cannot express statements about individual objects. Predicate logic extends propositional logic with predicates P(x) that describe properties of objects, and quantifiers: the universal quantifier (for all x, P(x)) and the existential quantifier (there exists x such that P(x)). Predicate logic is more expressive and forms the foundation of mathematical reasoning.

De Morgan's laws state: 1) The negation of a conjunction equals the disjunction of the negations: NOT(p AND q) is equivalent to (NOT p) OR (NOT q). 2) The negation of a disjunction equals the conjunction of the negations: NOT(p OR q) is equivalent to (NOT p) AND (NOT q). These laws also extend to quantifiers: NOT(for all x, P(x)) is equivalent to (there exists x, NOT P(x)), and vice versa. They are fundamental for simplifying logical expressions and writing proofs.

Modus ponens (affirming the antecedent) is a fundamental inference rule: given premises "if p then q" (p -> q) and "p is true", you can conclude "q is true". Example: Premise 1: "If it rains, the ground is wet" (p -> q). Premise 2: "It is raining" (p). Conclusion: "The ground is wet" (q). It is one of the most commonly used valid argument forms in both everyday reasoning and formal mathematical proof.

The conditional p -> q (if p then q) has this truth table: T->T = T, T->F = F, F->T = T, F->F = T. The only case where the conditional is false is when the antecedent (p) is true and the consequent (q) is false. This may seem counterintuitive because F->T = T, but this is the standard definition in classical logic: a false hypothesis implies anything (ex falso quodlibet).

Five proof methods are covered: 1) Direct proof -- deriving the conclusion directly from premises through a chain of inferences. 2) Proof by contradiction (reductio ad absurdum) -- assuming the negation of the conclusion and deriving a contradiction. 3) Mathematical induction -- proving a base case P(1) and an inductive step P(k)->P(k+1). 4) Proof by contrapositive -- proving NOT q -> NOT p instead of p -> q. 5) Existence proofs -- constructive (providing an explicit example) or non-constructive (showing non-existence leads to contradiction).

The power set P(A) of a set A is the set of all subsets of A, including the empty set and A itself. For A = {1, 2}, P(A) = {{}, {1}, {2}, {1, 2}}. The size of the power set is always 2 raised to the power of |A|, where |A| is the number of elements. So |P(A)| = 2^|A|. For a set with 3 elements, the power set has 2^3 = 8 subsets. This exponential relationship is fundamental in combinatorics and the theory of computation.

OR (inclusive disjunction) is true when at least one operand is true, including when both are true: T OR T = T. XOR (exclusive disjunction) is true when exactly one operand is true: T XOR T = F. In everyday language, "or" is often used exclusively ("tea or coffee?"), but in logic and programming, OR defaults to inclusive. XOR is important in digital circuits, cryptography (one-time pad), and error detection.

Yes, the Logic Reference is completely free with no usage limits, no account registration, and no software download required. All lookups run locally in your browser, so no data is ever transmitted to any server. It is part of liminfo.com's collection of free online education and mathematics tools.