Logic is the science of correct thinking and reasoning. Although on the YÖS exam logic constitutes a smaller section (approximately 14 problems), understanding logical operations, laws of logic, and rules of inference improves the overall ability to solve mathematical problems. Logic is also frequently used in proofs of theorems and in the analysis of mathematical statements.
---
Definition: A proposition (judgment, statement) is a sentence that can be either true or false, but not both at the same time.
Examples of propositions:- "2 + 2 = 4" — a true proposition (T or True)- "Moscow is the capital of France" — a false proposition (F or False)- "The Earth is round" — a true proposition (T)
Examples of non-propositions:- "What a beautiful sky!" — an exclamation, not a proposition- "Close the door" — a command, not a proposition- "$x > 5$" — an open sentence (depends on the value of $x$)
Notation:- T (true) or True or 1 — the proposition is true- F (false) or False or 0 — the proposition is false
Principle of bivalence: Every proposition has exactly one of two values: T or F.
Example 1: "5 is a prime number" — T
Example 2: "10 > 20" — F
Example 3: "$x^2 = 4$" — not a proposition (open sentence). But if we add a quantifier: "There exists $x$ such that $x^2 = 4$" — this is a proposition (T).
Definition: The conjunction of two propositions $A$ and $B$ is a new proposition that is true only when both original propositions are true.
Notation: $A \wedge B$ or $A$ AND $B$
Truth table:
| $A$ | $B$ | $A \wedge B$ ||-----|-----|-------------|| T | T | T || T | F | F || F | T | F || F | F | F |
Examples:- "The number 6 is even AND the number 6 is divisible by 3" — T (both conditions are satisfied)- "The number 6 is even AND the number 6 is divisible by 5" — F (the second condition is not satisfied)
Definition: The disjunction of two propositions $A$ and $B$ is a new proposition that is true when at least one of the original propositions is true.
Notation: $A \vee B$ or $A$ OR $B$
| $A$ | $B$ | $A \vee B$ ||-----|-----|-----------|| T | T | T || T | F | T || F | T | T || F | F | F |
Examples:- "It is raining today OR it is snowing today" — T, if at least one of them occurs- "The number 5 is even OR the number 5 is odd" — T (the second condition is satisfied)
Definition: The negation of a proposition $A$ is a new proposition that is true when $A$ is false, and false when $A$ is true.
Notation: $\neg A$ or $\overline{A}$ or NOT $A$
| $A$ | $\neg A$ ||-----|---------|| T | F || F | T |
Examples:- NOT "the number 5 is even" = "the number 5 is odd" — T- NOT "2 > 3" = "2 ≤ 3" — T
Definition: The implication (conditional proposition) $A \Rightarrow B$ ("if $A$, then $B$") is false only in one case: when $A$ is true and $B$ is false.
Notation: $A \Rightarrow B$ or $A \to B$
| $A$ | $B$ | $A \Rightarrow B$ ||-----|-----|-----------------|| T | T | T || T | F | F || F | T | T || F | F | T |
Terminology:- $A$ — premise (antecedent)- $B$ — conclusion (consequent)
Examples:- "If a number is divisible by 4, then it is divisible by 2" — T (correct consequence)- "If a number is divisible by 4, then it is odd" — F (there exist even numbers divisible by 4)
Definition: The equivalence of two propositions $A$ and $B$ ("$A$ if and only if $B$") is true when both propositions have the same truth value.
Notation: $A \Leftrightarrow B$ or $A \equiv B$
| $A$ | $B$ | $A \Leftrightarrow B$ ||-----|-----|--------------------|| T | T | T || T | F | F || F | T | F || F | F | T |
Examples:- "A number is divisible by 6 if and only if it is divisible by both 2 and 3" — T- "A number $n$ is even if and only if $n = 2k$ for some integer $k$" — T
Example: Construct the truth table for $(A \wedge B) \vee \neg C$
| $A$ | $B$ | $C$ | $A \wedge B$ | $\neg C$ | $(A \wedge B) \vee \neg C$ ||-----|-----|-----|------------|---------|------------------------|| T | T | T | T | F | T || T | T | F | T | T | T || T | F | T | F | F | F || T | F | F | F | T | T || F | T | T | F | F | F || F | T | F | F | T | T || F | F | T | F | F | F || F | F | F | F | T | T |
Example: $A \vee B \wedge C \Rightarrow D$ means $(A \vee (B \wedge C)) \Rightarrow D$
$$\neg(\neg A) \equiv A$$
Example: NOT(NOT "the number is even") = "the number is even"
$$\neg(A \wedge B) \equiv \neg A \vee \neg B$$$$\neg(A \vee B) \equiv \neg A \wedge \neg B$$
Examples:- NOT("the number is divisible by 2 AND the number is divisible by 3") = "the number is not divisible by 2 OR the number is not divisible by 3"- NOT("the number is positive OR the number is zero") = "the number is negative AND the number is not zero"
$$A \wedge A \equiv A$$$$A \vee A \equiv A$$
$$A \wedge B \equiv B \wedge A$$$$A \vee B \equiv B \vee A$$
$$(A \wedge B) \wedge C \equiv A \wedge (B \wedge C)$$$$(A \vee B) \vee C \equiv A \vee (B \vee C)$$
$$A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$$$$A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C)$$
$$A \vee (A \wedge B) \equiv A$$$$A \wedge (A \vee B) \equiv A$$
$$A \vee \text{T} \equiv \text{T}$$$$A \wedge \text{T} \equiv A$$$$A \vee \text{F} \equiv A$$$$A \wedge \text{F} \equiv \text{F}$$
Tautology: A proposition that is true for all values of the variables it contains.
Contradiction: A proposition that is false for all values of the variables it contains.
Satisfiable formula: A proposition that is true for some values of the variables.
Tautology: $A \vee \neg A$ (law of excluded middle)
| $A$ | $\neg A$ | $A \vee \neg A$ ||-----|---------|--------------|| T | F | T || F | T | T |
Contradiction: $A \wedge \neg A$ (law of non-contradiction)
| $A$ | $\neg A$ | $A \wedge \neg A$ ||-----|---------|-----------------|| T | F | F || F | T | F |
Satisfiable formula: $A \vee B$ (true when at least one variable is true)
Definition: Proposition $B$ is a logical consequence of proposition (or set of propositions) $A$ if, whenever $A$ is true, $B$ is also true.
Notation: $A \models B$ or $A \vdash B$
Relation to implication: $A \models B$ is equivalent to $A \Rightarrow B$ being a tautology.
Definition: Propositions $A$ and $B$ are logically equivalent if they have the same truth value for all values of the variables.
Notation: $A \equiv B$
Examples:- $\neg(A \vee B) \equiv \neg A \wedge \neg B$ (De Morgan's law)- $A \Rightarrow B \equiv \neg A \vee B$ (equivalence of implication)
Modus Ponens:$$\frac{A, A \Rightarrow B}{B}$$
If $A$ is true and "$A$ implies $B$", then $B$ is true.
Modus Tollens:$$\frac{\neg B, A \Rightarrow B}{\neg A}$$
If $B$ is false and "$A$ implies $B$", then $A$ is false.
Hypothetical syllogism:$$\frac{A \Rightarrow B, B \Rightarrow C}{A \Rightarrow C}$$
Definition: The universal quantifier $\forall$ (for all) is used for statements that hold for all elements of a set.
Notation: $\forall x: P(x)$ or $\forall x \in S: P(x)$
Read as: "For all $x$, $P(x)$ holds" or "For every $x$ in $S$, $P(x)$ holds"
Examples:- $\forall x \in \mathbb{R}: x^2 \geq 0$ — "For all real numbers $x$, $x^2 \geq 0$" — T- $\forall n \in \mathbb{N}: n > 0$ — "For all natural numbers $n$, $n > 0$" — T (if we start from 1)
Definition: The existential quantifier $\exists$ (there exists) is used for statements that hold for at least one element of a set.
Notation: $\exists x: P(x)$ or $\exists x \in S: P(x)$
Read as: "There exists $x$ such that $P(x)$" or "There exists $x$ in $S$ such that $P(x)$"
Examples:- $\exists x \in \mathbb{R}: x^2 = 4$ — "There exists a real number $x$ such that $x^2 = 4$" — T (for example, $x = 2$)- $\exists x \in \mathbb{R}: x^2 = -1$ — "There exists a real number $x$ such that $x^2 = -1$" — F
De Morgan's law for quantifiers:
$$\neg(\forall x: P(x)) \equiv \exists x: \neg P(x)$$
The negation of "for all $x$, $P(x)$ holds" is equivalent to "there exists $x$ for which $P(x)$ does not hold"
$$\neg(\exists x: P(x)) \equiv \forall x: \neg P(x)$$
The negation of "there exists $x$ for which $P(x)$ holds" is equivalent to "for all $x$, $P(x)$ does not hold"
Examples:- NOT($\forall x \in \mathbb{R}: x > 0$) $\equiv$ $\exists x \in \mathbb{R}: x \leq 0$ — T- NOT($\exists x \in \mathbb{R}: x^2 < 0$) $\equiv$ $\forall x \in \mathbb{R}: x^2 \geq 0$ — T
Statement: Determine whether the proposition is true or false:"$2 + 2 = 4$ AND $3 > 5$"
Solution:- "$2 + 2 = 4$" — T- "$3 > 5$" — F- T $\wedge$ F = F
Answer: False
Statement: Construct the truth table for $A \Rightarrow (B \vee \neg A)$
| $A$ | $B$ | $\neg A$ | $B \vee \neg A$ | $A \Rightarrow (B \vee \neg A)$ ||-----|-----|---------|----------------|---------------------------|| T | T | F | T | T || T | F | F | F | F || F | T | T | T | T || F | F | T | T | T |
Answer: This is a satisfiable formula (neither a tautology nor a contradiction).
Statement: Simplify $\neg(A \vee (B \wedge C))$
Solution:$$\neg(A \vee (B \wedge C)) \equiv \neg A \wedge \neg(B \wedge C)$$$$\equiv \neg A \wedge (\neg B \vee \neg C)$$
Answer: $\neg A \wedge (\neg B \vee \neg C)$
Statement: Write the negation of the proposition:"For all natural numbers $n$, $n^2 > n$ holds"
Solution:Original: $\forall n \in \mathbb{N}: n^2 > n$
Negation: $\neg(\forall n \in \mathbb{N}: n^2 > n) \equiv \exists n \in \mathbb{N}: n^2 \leq n$
This is true: for $n = 1$ we have $1^2 = 1$, that is, $n^2 \leq n$ holds.
Answer: "There exists a natural number $n$ such that $n^2 \leq n$"
Statement: Is it true that "$A \Rightarrow C$" follows from "$A \Rightarrow B$" and "$B \Rightarrow C$"?
Solution:This is the hypothetical syllogism.
Suppose $A$ is true.- From $A \Rightarrow B$ and the truth of $A$, it follows that $B$ is true.- From $B \Rightarrow C$ and the truth of $B$, it follows that $C$ is true.- Hence, $C$ follows from $A$, i.e., $A \Rightarrow C$ is true.
Answer: Yes, it is true. $(A \Rightarrow B) \wedge (B \Rightarrow C) \vdash (A \Rightarrow C)$
Wrong: "$A \Rightarrow B$" and "$A \Leftrightarrow B$" are the same thing.
Correct: - $A \Rightarrow B$ is false only when $A$ is true and $B$ is false- $A \Leftrightarrow B$ is true only when $A$ and $B$ have the same values
Wrong: $\neg(A \vee B) = \neg A \vee \neg B$
Correct: $\neg(A \vee B) = \neg A \wedge \neg B$
Wrong: The negation of "for all" remains "for all".
Correct: $\neg(\forall x: P(x)) = \exists x: \neg P(x)$
Wrong: "$A \Rightarrow B$" can be computed as $A \wedge B$.
Correct: "$A \Rightarrow B$" is equivalent to $\neg A \vee B$.
Wrong: "$A \vee B \wedge C$" is interpreted as "$(A \vee B) \wedge C$".
Correct: "$A \vee B \wedge C$" means "$A \vee (B \wedge C)$" (conjunction has priority).
The basic truth tables for $\wedge$, $\vee$, $\neg$, $\Rightarrow$, $\Leftrightarrow$ are the foundation of logic. Memorize them.
They frequently appear in problems on simplifying logical formulas.
$A \Rightarrow B \equiv \neg A \vee B$ — this is very useful for transformations.
$\neg \forall = \exists$ and $\neg \exists = \forall$ — this is frequently tested.
If you are unsure of the answer, draw a full truth table. This is a reliable method.
The ability to simplify complex logical formulas saves time on the exam.
Logic is the discipline of correct thinking, and understanding it improves the ability to solve all types of mathematical problems. From simple truth tables to complex quantified statements, these skills develop logical thinking and help avoid errors in reasoning. Although logic constitutes a small part of the YÖS exam, mastering it strengthens your mathematical foundations and helps in solving more complex problems in other sections. Memorize the basic definitions, laws, and rules, and practice constantly in constructing truth tables and simplifying formulas.
All course topics · Practice problems
Please enable JavaScript to use the practice app.