Logic Connectives and Quantifiers

Propositions and the five connectives

A proposition is a statement that is definitely true or definitely false, such as seven is prime. Propositional logic builds larger statements from these atoms using five connectives. Negation, not p, written with the sign not, flips a truth value. Conjunction, p and q, written with a wedge, is true only when both parts are true. Disjunction, p or q, written with a vee, is true when at least one part is true, including when both are.

Two connectives express relationships. The conditional, if p then q, written p implies q, is false in exactly one case, when p is true but q is false; otherwise it is true. The biconditional, p if and only if q, is true precisely when both parts share the same truth value. Because each connective is defined by when it comes out true, a truth table captures every one of them.

• Negation flips a truth value; conjunction is true only when both parts are true.
• Disjunction is true when at least one part is true.
• The conditional is false only when a true premise gives a false conclusion.
• The biconditional is true when both sides share a truth value.

Precedence: reading a formula without parentheses

Just as arithmetic multiplies before it adds, logic has an order of precedence so that formulas are not drowning in brackets. Negation binds most tightly, then conjunction, then disjunction, then the conditional, and finally the biconditional binds most loosely. So not p and q means take the negation of p first and then conjoin, rather than negating the whole conjunction.

Precedence removes ambiguity but not all of it. The conditional is usually taken to associate to the right, yet a chain of conditionals is where a stray reading changes the meaning, so most writers add parentheses. The safe habit is to lean on precedence for common cases and parenthesise anything a reader might misgroup.

• Precedence, tightest first: negation, then conjunction, then disjunction, then the conditional, then the biconditional.
• So negating p and q affects only p before the conjunction is applied.
• Add parentheses whenever a reader might group a formula differently.

The conditional and its relatives

The conditional deserves special care because it trips up beginners. If p then q makes no claim at all when p is false; in that case the whole statement is vacuously true. This matches everyday promises: if you never trigger the condition, the promise is not broken. The one way to make a conditional false is to satisfy the premise yet fail the conclusion.

From if p then q you can form three related statements. The converse, if q then p, and the inverse, if not p then not q, are not equivalent to the original, a common source of faulty reasoning. The contrapositive, if not q then not p, is always equivalent to the original, which is why proof by contrapositive is a legitimate strategy.

Quantifiers: speaking about many objects

Predicate logic adds variables and quantifiers so a single sentence can range over a whole domain. The universal quantifier, for all x, asserts that a property holds for every object in the domain, while the existential quantifier, there exists an x, asserts that at least one object has the property. The domain matters: for all x, x squared is at least zero, is true over the real numbers, but its truth depends entirely on which objects x is allowed to range over.

A quantifier binds its variable, so the x in for all x, P of x, is a placeholder with no meaning outside the sentence, much like a loop variable. A variable not bound by any quantifier is called free, and a statement with free variables is neither true nor false until those variables are given values or quantified.

Nesting and negating quantifiers

When quantifiers are nested, their order is not decorative. For every x there exists a y such that x plus y equals zero is true over the integers, since each x has its own y. Swap the order to there exists a y such that for every x, x plus y equals zero, and the claim becomes false, because now one fixed y would have to work for every x. Read nested quantifiers left to right, in the order written.

Negation flips quantifiers in a clean, mechanical way, the quantifier version of De Morgan's laws. The negation of for all x, P of x, is there exists an x for which P of x fails, and the negation of there exists an x, P of x, is for all x, P of x fails. Pushing a negation inward turns every for all into a there exists and vice versa, negating the predicate at the end.

• Nested quantifiers depend on order: for-all then there-exists can differ from there-exists then for-all.
• Negating for all x, P of x gives there exists an x with not P of x.
• Negating there exists x, P of x gives for all x, not P of x.
• To negate, swap each quantifier and negate the inner statement.

Putting logic to work

These pieces combine into the statements you actually prove. A definition like a function is injective when for all a and b, f of a equals f of b implies a equals b, is a nested quantifier wrapped around a conditional, and knowing how to negate it tells you exactly what a counterexample must look like. Truth tables handle the propositional layer, checking whether a compound statement is always true or whether two forms are equivalent.

The payoff is that logic turns vague arguments into checkable ones. When you can read a claim as connectives and quantifiers, you know what would confirm it and what would refute it, which is the whole game in writing proofs. Practising with truth tables and then the proof trainer makes the notation second nature.