Propositional and Predicate Logic: every key term you need (+ practice quiz)
25 flashcard terms for Discrete Mathematics Topic 1, written to match the course framework. Study them here, then drill them as interactive flashcards, or test yourself with the 15-question quiz — free, no account needed.
A declarative statement that is definitely either true or false, but not both. Questions, commands and statements with free variables are not propositions until the variables are given values.
Truth value
The assignment of either true or false to a proposition. In discrete mathematics the two values are usually written T and F, or 1 and 0 when logic is being connected to circuit design.
Negation
The connective written as not p, true exactly when p is false and false exactly when p is true. It is the only standard connective that takes a single input rather than two.
Conjunction
The connective p and q, true only in the single row of the truth table where both p and q are true, and false in the other three rows.
Disjunction
The inclusive or connective p or q, true whenever at least one of p and q is true, and false only when both are false. Everyday English often means the exclusive version instead.
Exclusive or
The connective true exactly when p and q have different truth values. It is equivalent to the negation of the biconditional, and it behaves like addition of bits with carry discarded.
Conditional statement
The statement if p then q, false only when the hypothesis p is true and the conclusion q is false. Because a false hypothesis makes it true, it is called vacuously true in that case.
Biconditional
The statement p if and only if q, true exactly when p and q share the same truth value. It is logically equivalent to the conjunction of the conditional and its converse.
Converse
The statement obtained from if p then q by swapping hypothesis and conclusion, giving if q then p. A conditional and its converse are not logically equivalent, which is a very common source of error.
Contrapositive
The statement obtained from if p then q by swapping and negating both parts, giving if not q then not p. It is logically equivalent to the original conditional, which is what makes contrapositive proof valid.
Inverse of a conditional
The statement formed by negating both parts of if p then q without swapping them, giving if not p then not q. It is equivalent to the converse but not to the original conditional.
Tautology
A compound proposition that is true under every possible assignment of truth values to its variables. The law of the excluded middle, p or not p, is the standard example.
Contradiction in logic
A compound proposition false under every assignment of truth values, such as p and not p. Its negation is always a tautology, and it is the target of a proof by contradiction.
Contingency
A compound proposition that is true under some assignments of truth values and false under others, so it is neither a tautology nor a contradiction.
Logical equivalence
Two compound propositions are logically equivalent when they have identical truth values in every row of the truth table, equivalently when their biconditional is a tautology.
De Morgan laws
The pair of equivalences stating that the negation of a conjunction is the disjunction of the negations, and the negation of a disjunction is the conjunction of the negations.
Distributive laws of logic
The equivalences that let and distribute over or and or distribute over and. Unlike ordinary arithmetic, both directions of distribution hold in propositional logic.
Predicate
A statement containing one or more free variables that becomes a proposition once each variable is given a value from the domain, or once each variable is bound by a quantifier.
Domain of discourse
The set of values a quantified variable is allowed to take. Quantified statements have no meaning until the domain is fixed, and changing the domain can flip the truth value.
Universal quantifier
The symbol read as for all, asserting that a predicate holds for every element of the domain. A single element where the predicate fails is enough to make the whole statement false.
Existential quantifier
The symbol read as there exists, asserting that a predicate holds for at least one element of the domain. Producing one such element is a complete proof of the statement.
Counterexample
A specific element of the domain for which a universally quantified claim fails. One counterexample disproves the claim entirely, while any number of confirming examples never proves it.
Quantifier negation rules
Negating a for all statement gives there exists an element where the predicate fails, and negating a there exists statement gives for all elements the predicate fails.
Nested quantifiers
Two or more quantifiers applied in sequence to a multivariable predicate. Order matters when the quantifiers differ, since for all x there exists y is far weaker than there exists y for all x.
Rules of inference
Argument patterns guaranteed to preserve truth, including modus ponens, modus tollens, hypothetical syllogism and resolution. An argument is valid when its conclusion follows from its premises by such rules.