01 Logic and Quantifiers

Propositions and Statements

A proposition is a declarative sentence with exactly one truth value: true or false. Examples include “7 is prime,” which is true, and “10 is less than 3,” which is false. A command such as “Close the door” and a question such as “Is the test tomorrow?” are not propositions.

An expression such as $x+2=5$ is not yet a proposition when the value of $x$ is unspecified. Its truth depends on the value assigned to the variable, so it is instead an open statement or predicate expression.

Propositions are often represented by lowercase letters such as $p$, $q$, and $r$. Combining propositions produces compound propositions. For example, if $p$ means “the number is positive” and $q$ means “the number is even,” then “the number is positive and even” is represented by $p\land q$.

Takeaway: Before manipulating a statement, determine whether it already has a definite truth value or whether it still depends on variables.

Logical Connectives

A logical connective forms a compound proposition from simpler propositions. The main connectives are:

• Negation: $\neg p$, meaning “not $p$.” It reverses the truth value of $p$.

• Conjunction: $p\land q$, meaning “$p$ and $q$.” It is true only when both components are true.

• Disjunction: $p\lor q$, meaning “$p$ or $q$.” In mathematical logic, this is inclusive: it is true when at least one component is true, including when both are true.

• Conditional: $p\to q$, meaning “if $p$, then $q$.” It is false only when $p$ is true and $q$ is false.

• Biconditional: $p\leftrightarrow q$, meaning “$p$ if and only if $q$.” It is true when the two components have the same truth value.

The conditional $p\to q$ is not generally the same as its converse $q\to p$. For example, divisibility by $4$ implies being even, but being even does not imply divisibility by $4$. A biconditional asserts both directions:

Takeaway: Pay particular attention to the direction of a conditional and to whether “or” is intended inclusively.

Truth Tables and Evaluation

A truth table evaluates a compound proposition by listing every possible assignment of truth values to its components. For two propositions, the four rows are the assignments $TT$, $TF$, $FT$, and $FF$. The basic behavior is:

• $p\land q$ is true only in the $TT$ row.

• $p\lor q$ is false only in the $FF$ row.

• $p\to q$ is false only in the $TF$ row.

• $p\leftrightarrow q$ is true in the $TT$ and $FF$ rows.

To evaluate a longer expression, calculate its smaller components first. For example, for $(p\land q)\to p$, first determine $p\land q$, then compare that result with $p$. The final column is true in every row, so the expression is a tautology.

Unless parentheses specify otherwise, use this precedence order:

1. $\neg$

2. $\land$

3. $\lor$

4. $\to$

5. $\leftrightarrow$

Thus, $\neg p\lor q\land r$ means $(\neg p)\lor(q\land r)$. Parentheses are preferable whenever the intended grouping could be unclear.

Takeaway: Truth tables provide a systematic method for checking every possible case rather than relying on intuition.

Equivalence and Logical Laws

Two expressions have logical equivalence when they match in truth value for every possible assignment. This relationship is written $P\equiv Q$. It can be demonstrated with a truth table or by applying logical laws.

Important laws include double negation, $\neg(\neg p)\equiv p$, the conditional equivalence $p\to q\equiv\neg p\lor q$, and the contrapositive equivalence $p\to q\equiv\neg q\to\neg p$. De Morgan’s laws are:

For example, simplify $\neg(p\lor\neg q)$ by applying De Morgan’s law and then double negation:

A proposition that is always true is a tautology. A proposition that is always false is a contradiction. If its truth value changes across assignments, it is contingent.

Takeaway: When simplifying, change one recognizable subexpression at a time and name the law that justifies each step.

Predicates, Domains, and Quantifiers

A predicate is a statement involving variables whose truth depends on assigned values. For example, $P(x): x>5$ is true for $x=7$ and false for $x=3$. It becomes a proposition when a value is substituted or when a quantifier binds the variable.

The domain of discourse specifies the objects under consideration. A relation such as $R(x,y):x<y$ is a predicate with two variables. Always state the domain because the interpretation of a predicate depends on which objects are allowed.

Quantifiers turn predicates into propositions:

• The universal quantifier $\forall$ means “for every.” The statement $\forall x\in D\;P(x)$ claims that every element of $D$ satisfies $P$.

• The existential quantifier $\exists$ means “there exists at least one.” The statement $\exists x\in D\;P(x)$ claims that at least one element of $D$ satisfies $P$.

• Unique existence, written $\exists!x\;P(x)$, means that exactly one value satisfies the predicate.

For example, $\exists n\in\mathbb Z\;(n^2=9)$ is true because $n=3$ and $n=-3$ are witnesses. By contrast, $\exists!x\in\mathbb R\;(x+2=5)$ is true because the only solution is $x=3$.

Takeaway: A quantified statement is meaningful only when the variables, predicates, and domain are all clear.

Negating Quantified Statements

Negating a quantified statement requires both reversing the quantifier and negating the predicate:

In words, “not everything has property $P$” means “at least one thing does not have property $P$,” while “nothing has property $P$” means “everything lacks property $P$.”

Negating comparisons also requires care. The negation of $x>3$ is $x\le 3$; the negation of $x\ge 3$ is $x<3$; and the negation of $x=3$ is $x\ne 3$. For example, the negation of

is

The negated statement is false, because no real number has a negative square.

Takeaway: To negate a quantified claim, reverse $\forall$ and $\exists$, then negate the condition accurately.

Translating English into Formal Logic

Formal translation begins with the domain and the meanings of the predicates. Then identify indicator words, preserve the logical structure, and check the scope of each quantifier.

For “Every integer is rational,” let $I(x)$ mean “$x$ is an integer” and $R(x)$ mean “$x$ is rational.” The correct form is:

The implication matters: the statement says that anything which is an integer is rational, not that every object is an integer.

For “Some integer is even and prime,” if $E(x)$ means “$x$ is even” and $P(x)$ means “$x$ is prime,” write:

A witness is $x=2$. For “Only registered users may access the system,” let $R(x)$ mean “$x$ is registered” and $A(x)$ mean “$x$ may access the system.” The word “only” introduces a necessary condition:

With multiple quantifiers, order changes meaning. The statement $\forall x\exists y\;R(x,y)$ allows a different $y$ for each $x$, whereas $\exists y\forall x\;R(x,y)$ requires one particular $y$ that works for every $x$. Over the integers, if $R(x,y)$ means $x<y$, the first statement is true but the second is false.

Use this checklist:

1. Identify the domain.

2. Define every predicate and relation.

3. Locate words such as “every,” “some,” “no,” “only,” and “exactly one.”

4. Translate conjunctions, disjunctions, negations, and implications.

5. Check parentheses, scope, and quantifier order.

6. Test the result with a witness or counterexample.

Takeaway: Most translation errors come from a reversed implication, an omitted domain, or an incorrect quantifier scope.