Logic Syllabus

State the rule of modus tollens.

From $p \to q$ and $\neg q$, infer $\neg p$. Formally: $\dfrac{p \to q,\; \neg q}{\therefore \neg p}$.

State the rule of hypothetical syllogism.

From $p \to q$ and $q \to r$, infer $p \to r$.

State the rule of disjunctive syllogism.

From $p \vee q$ and $\neg p$, infer $q$.

State the resolution rule of inference.

From $p \vee q$ and $\neg p \vee r$, infer $q \vee r$. Resolution is the basis of automated theorem proving and refutation-based SAT solving.

What is a valid argument, and what does validity guarantee about the conclusion?

An argument is valid if whenever all premises are true the conclusion must be true, i.e. $(P_1 \wedge \cdots \wedge P_n) \to C$ is a tautology. Validity concerns form, not the actual truth of the premises.

Define the universal and existential quantifiers.

Universal $\forall x\, P(x)$ means "$P(x)$ is true for every $x$ in the domain"; existential $\exists x\, P(x)$ means "$P(x)$ is true for at least one $x$ in the domain."

State the rules for negating quantifiers (generalized De Morgan).

$\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$ and $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$.

How do you express "every $x$ satisfying $P$ also satisfies $Q$" using quantifiers?

$\forall x\, (P(x) \to Q(x))$. Universal statements over a condition use a conditional; existential statements over a condition use conjunction: $\exists x\,(P(x) \wedge Q(x))$.

Does the order of nested quantifiers of different types matter? Illustrate.

Yes. $\forall x\,\exists y\, P(x,y)$ (each $x$ has some $y$) generally differs from $\exists y\,\forall x\, P(x,y)$ (one $y$ works for all $x$). The latter implies the former, but not conversely.

What is the negation of $\forall x\, \exists y\, P(x,y)$?

$\exists x\, \forall y\, \neg P(x,y)$. Push the negation inward, flipping each quantifier.

State the universal instantiation and universal generalization rules.

Universal instantiation: from $\forall x\, P(x)$ infer $P(c)$ for any element $c$. Universal generalization: from $P(c)$ proved for an arbitrary $c$, infer $\forall x\, P(x)$.

State the existential instantiation and existential generalization rules.

Existential instantiation: from $\exists x\, P(x)$ introduce a new witness $c$ with $P(c)$. Existential generalization: from $P(c)$ for some particular $c$, infer $\exists x\, P(x)$.

What is a direct proof of $p \to q$?

Assume $p$ is true, then use definitions, axioms, and prior results through a chain of valid inferences to show that $q$ must be true.

Describe proof by contraposition and when it is used.

To prove $p \to q$, instead prove the equivalent contrapositive $\neg q \to \neg p$: assume $\neg q$ and derive $\neg p$. Useful when the negations are easier to work with than the originals.

Describe proof by contradiction.

To prove a statement $S$, assume $\neg S$ and derive a contradiction (something of the form $r \wedge \neg r$); this forces $\neg S$ to be false, so $S$ is true.

What is a proof by cases (exhaustive proof)?

Split the hypothesis into finitely many exhaustive cases and prove the conclusion in each. Valid because $(p_1 \vee \cdots \vee p_n) \to q \equiv (p_1 \to q) \wedge \cdots \wedge (p_n \to q)$.

How do you disprove a universally quantified statement $\forall x\, P(x)$?

Provide a counterexample: a specific element $c$ in the domain for which $P(c)$ is false, since this establishes $\exists x\, \neg P(x)$.

Define set equality and the subset relation.

$A = B$ iff they have exactly the same elements, i.e. $\forall x\,(x \in A \leftrightarrow x \in B)$. $A \subseteq B$ iff $\forall x\,(x \in A \to x \in B)$; $A \subset B$ is a proper subset ($A \subseteq B$ and $A \neq B$).

What is the power set of a set $A$, and its cardinality for a finite set?

The power set $\mathcal{P}(A)$ is the set of all subsets of $A$. If $|A| = n$ then $|\mathcal{P}(A)| = 2^{n}$.

Define the union, intersection, and difference of sets $A$ and $B$.

$A \cup B = \{x : x \in A \vee x \in B\}$; $A \cap B = \{x : x \in A \wedge x \in B\}$; $A \setminus B = \{x : x \in A \wedge x \notin B\}$.

State De Morgan's laws for set complements.

$\overline{A \cup B} = \overline{A} \cap \overline{B}$ and $\overline{A \cap B} = \overline{A} \cup \overline{B}$.

State the inclusion–exclusion principle for two sets.

$|A \cup B| = |A| + |B| - |A \cap B|$.

Define the Cartesian product $A \times B$ and give its cardinality.

$A \times B = \{(a,b) : a \in A,\; b \in B\}$, the set of ordered pairs. For finite sets $|A \times B| = |A|\cdot|B|$.

Define a binary relation from $A$ to $B$.

A binary relation from $A$ to $B$ is any subset $R \subseteq A \times B$. When $A = B$ it is called a relation on $A$.

List the three defining properties of an equivalence relation.

Reflexive ($\forall a,\; aRa$), symmetric ($aRb \to bRa$), and transitive ($aRb \wedge bRc \to aRc$). An equivalence relation partitions the set into equivalence classes.

What properties define a partial order?

Reflexive, antisymmetric ($aRb \wedge bRa \to a=b$), and transitive. A set with a partial order is a partially ordered set (poset).

Define a function $f: A \to B$ and the terms domain and codomain.

A function $f: A \to B$ assigns to each element $x \in A$ exactly one element $f(x) \in B$. $A$ is the domain, $B$ is the codomain, and the range is $\{f(x) : x \in A\} \subseteq B$.

Define injective, surjective, and bijective functions.

Injective (one-to-one): $f(a)=f(b) \Rightarrow a=b$. Surjective (onto): range equals codomain, $\forall y\in B\,\exists x\, f(x)=y$. Bijective: both injective and surjective, and hence invertible.

What does it mean for two sets to have the same cardinality, and how is a countably infinite set defined?

$|A| = |B|$ iff there is a bijection $f: A \to B$. A set is countably infinite if it has the same cardinality as $\mathbb{N}$ (denoted $\aleph_0$); countable means finite or countably infinite.

State Cantor's theorem and its consequence for $|\mathbb{R}|$.

For any set $A$, $|A| < |\mathcal{P}(A)|$, so no set can biject with its power set. Consequently $\mathbb{R}$ is uncountable, with $|\mathbb{R}| = 2^{\aleph_0} > \aleph_0$; Cantor's diagonal argument shows $(0,1)$ is uncountable.

In modal logic, what do the operators $\Box$ and $\Diamond$ mean, and how are they related?

$\Box p$ means "$p$ is necessarily true" and $\Diamond p$ means "$p$ is possibly true." They are dual: $\Diamond p \equiv \neg \Box \neg p$ and $\Box p \equiv \neg \Diamond \neg p$.

What are the components of a Kripke model (frame plus valuation)?

A Kripke model is a triple $\langle W, R, V \rangle$: $W$ a non-empty set of possible worlds, $R \subseteq W \times W$ an accessibility relation, and $V$ a valuation assigning to each world the propositions true there.

State the Kripke truth conditions for $\Box$ and $\Diamond$ at a world $w$.

$w \models \Box p$ iff for all $v$ with $wRv$, $v \models p$ (true in all accessible worlds). $w \models \Diamond p$ iff there exists $v$ with $wRv$ and $v \models p$ (true in some accessible world).

Which properties of the accessibility relation correspond to modal axioms T, 4, and 5?

Axiom T ($\Box p \to p$) corresponds to reflexivity; axiom 4 ($\Box p \to \Box\Box p$) to transitivity; axiom 5 ($\Diamond p \to \Box\Diamond p$) to Euclideanness. Reflexive + transitive + symmetric (equivalence relation) gives system S5.