AP Subject A Essentials 2: Logic, Sets, Truth Tables, and De Morgan's Laws
Sets and Venn diagrams, logical operations and precedence, implication, truth tables, and De Morgan's laws for AP Subject A, with worked examples and original practice questions.
AP Subject A · Installment 2 · An independent study resource for the 2026 exam and Syllabus Ver.7.2. It is not affiliated with IPA and does not guarantee a pass. Open the series hub
Scope and disclaimer This installment is written for 2026 exam preparation, and its scope follows the official IPA Applied Information Technology Engineer Examination (Level 3) syllabus Ver.7.2. Motitory is not affiliated with IPA (Information-technology Promotion Agency, Japan), and this article is not reviewed or approved by IPA. Studying with this article does not guarantee a passing result. All exercises are Motitory originals, not official IPA past questions. Before your exam, check the IPA website for the latest syllabus and exam information.
Contents
- Learning objectives
- Syllabus Ver.7.2 mapping
- Terminology map (English / Japanese / Korean)
- Sets and Venn diagrams
- Propositions and truth values
- Logical operations: NOT, AND, OR, XOR, NAND, NOR
- Precedence and parentheses
- Implication
- Building and comparing truth tables
- De Morgan’s laws and other basic laws
- Worked examples
- Common traps
- Practice questions (Motitory originals)
- Final self-check and review plan
- Sources
1. Learning objectives
After this installment, you should be able to:
- read set notation (∪, ∩, complement, ⊆) and identify the matching region of a Venn diagram;
- explain what a proposition and a truth value are;
- evaluate NOT, AND, OR, XOR, NAND, and NOR, and apply operator precedence correctly;
- build a truth table and use it to decide whether two expressions are equivalent;
- apply De Morgan’s laws in both set form and propositional form;
- spot the typical traps in Subject A questions on this topic.
2. Syllabus Ver.7.2 mapping
This installment covers the following items of the IPA syllabus Ver.7.2:
- 大分類1：基礎理論／中分類1：基礎理論／1. 離散数学／（4）集合と命題 (Major category 1: Basic theory / Middle category 1: Basic theory / 1. Discrete mathematics / (4) Sets and propositions)
- 大分類1：基礎理論／中分類1：基礎理論／1. 離散数学／（5）論理演算 (Major category 1: Basic theory / Middle category 1: Basic theory / 1. Discrete mathematics / (5) Logical operations)
Karnaugh maps, which also appear in item (5), are not covered in this installment.
3. Terminology map (English / Japanese / Korean)
Exam questions are written in Japanese, so learn the Japanese term together with the concept.
| English | Japanese | Korean |
|---|---|---|
| set | 集合 | 집합 |
| element | 要素 | 원소 |
| universal set | 全体集合 | 전체집합 |
| empty set | 空集合 | 공집합 |
| union | 和集合 | 합집합 |
| intersection | 積集合 | 교집합 |
| complement | 補集合 | 여집합 |
| subset | 部分集合 | 부분집합 |
| Venn diagram | ベン図 | 벤 다이어그램 |
| proposition | 命題 | 명제 |
| truth value | 真理値 | 진릿값 |
| true / false | 真／偽 | 참 / 거짓 |
| negation (NOT) | 否定 | 부정 |
| OR (disjunction) | 論理和 | 논리합 |
| AND (conjunction) | 論理積 | 논리곱 |
| XOR (exclusive OR) | 排他的論理和 | 배타적 논리합 |
| NOR | 否定論理和 | 부정 논리합 |
| NAND | 否定論理積 | 부정 논리곱 |
| implication | 含意 | 함의 |
| truth table | 真理値表 | 진리표 |
| De Morgan’s laws | ド・モルガンの法則 | 드모르간의 법칙 |
| distributive law | 分配則 | 분배 법칙 |
| logical function | 論理関数 | 논리 함수 |
4. Sets and Venn diagrams
A set is a collection of clearly defined elements. The set that contains every element under discussion is the universal set U.
| Notation | Meaning | Elements included |
|---|---|---|
| A ∪ B | union | in A or in B (or both) |
| A ∩ B | intersection | in A and in B |
| Aᶜ | complement | in U but not in A |
| A ⊆ B | subset | every element of A is also in B |
| A − B | difference | in A but not in B (= A ∩ Bᶜ) |
Notation note: in this article the complement of X is written Xᶜ. Exam questions often draw a bar over the set (or expression) instead; the meaning is the same.
Venn interpretation. Two sets A and B divide U into four regions:
| Region | Set expression |
|---|---|
| A only | A ∩ Bᶜ |
| B only | Aᶜ ∩ B |
| both | A ∩ B |
| neither | Aᶜ ∩ Bᶜ |
Any expression built from A, B, ∪, ∩, and complements is just a choice of some of these four regions. To compare two set expressions, list which regions each one shades.
Counting elements. The number of elements in the union is |A ∪ B| = |A| + |B| − |A ∩ B|. The intersection is subtracted because it would otherwise be counted twice. Also remember that the “neither” region may be non-empty: |U| = |A ∪ B| + |Aᶜ ∩ Bᶜ|.
5. Propositions and truth values
A proposition is a statement that is definitely either true or false. “7 is a prime number” is a proposition (true). “x is greater than 3” is not a proposition until the value of x is fixed.
Whether a proposition is true or false is its truth value. In logical operations, true is usually written as 1 and false as 0.
Sets and propositions correspond closely. If you treat “the element is in A” as a proposition, the operations line up as follows:
| Sets | Logic |
|---|---|
| A ∪ B | A OR B |
| A ∩ B | A AND B |
| Aᶜ | NOT A |
| U (universal set) | 1 (always true) |
| ∅ (empty set) | 0 (always false) |
| A ⊆ B | A → B is always true |
The four Venn regions in Section 4 also correspond to the four input rows (A, B) = (1, 0), (0, 1), (1, 1), (0, 0) of a truth table.
6. Logical operations: NOT, AND, OR, XOR, NAND, NOR
Common notations: NOT A is written ¬A or with a bar over A; A AND B as A ∧ B or A · B; A OR B as A ∨ B or A + B; A XOR B as A ⊕ B. This article uses ¬, ∧, ∨, and ⊕.
| A | B | ¬A | A ∧ B | A ∨ B | A ⊕ B | ¬(A ∧ B) NAND | ¬(A ∨ B) NOR |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 |
Key points:
- AND is 1 only when both inputs are 1.
- OR is 1 when at least one input is 1. It is inclusive: 1 ∨ 1 = 1. In the “+” notation, 1 + 1 = 1, not 2.
- XOR is 1 only when the inputs differ. It is the exclusive OR.
- NAND and NOR are the negations of AND and OR.
7. Precedence and parentheses
The common convention is: NOT first, then AND, then OR. So
A ∨ B ∧ ¬C means A ∨ (B ∧ (¬C)).
In “+ and ·” notation this works like ordinary arithmetic: A + B · C means A + (B · C).
Rules to follow in the exam:
- If the question defines the precedence or the meaning of its symbols, follow the question.
- The position of XOR in the precedence order is not uniform across textbooks, so expressions that mix XOR with other operators usually need parentheses. When you rewrite an expression yourself, add parentheses whenever there is any doubt.
- ¬ applies only to what immediately follows it: ¬A ∧ B is (¬A) ∧ B, which differs from ¬(A ∧ B). When a bar is drawn over a whole expression, the negation covers everything under the bar.
8. Implication
“If A, then B” is written A → B (implication).
| A | B | A → B |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
- A → B is false only when A is true and B is false.
- A → B is equivalent to ¬A ∨ B.
- In set terms, “A → B is always true” means A ⊆ B.
- The converse B → A is not equivalent to A → B (check the rows (0, 1) and (1, 0)).
9. Building and comparing truth tables
- With n input variables, the table has 2ⁿ rows (2 variables: 4 rows; 3 variables: 8 rows).
- List the inputs systematically, like counting in binary: 00, 01, 10, 11 (for 3 variables: 000 to 111). This prevents missing rows.
- Add one column for each intermediate part of the expression, working from the inside of the parentheses outward.
- Two expressions are equivalent only if their result columns match on every row. A single mismatched row proves they are not equivalent; that row is a counterexample.
10. De Morgan’s laws and other basic laws
De Morgan’s laws — negate each term and swap the operator.
| Set form | Propositional form |
|---|---|
| (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ | ¬(A ∨ B) = ¬A ∧ ¬B |
| (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ | ¬(A ∧ B) = ¬A ∨ ¬B |
In words: “not (A or B)” = “neither A nor B”; “not (A and B)” = “at least one of them is not”.
Truth-table check of the propositional form:
| A | B | ¬(A ∨ B) | ¬A ∧ ¬B | ¬(A ∧ B) | ¬A ∨ ¬B |
|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 | 0 |
The columns match on every row, so both laws hold.
Other basic laws (each also holds with ∪, ∩, U, ∅ in place of ∨, ∧, 1, 0):
| Law | Form |
|---|---|
| Double negation | ¬¬A = A |
| Complement | A ∨ ¬A = 1, A ∧ ¬A = 0 |
| Identity | A ∨ 0 = A, A ∧ 1 = A |
| Domination | A ∨ 1 = 1, A ∧ 0 = 0 |
| Idempotent | A ∨ A = A, A ∧ A = A |
| Commutative / associative | order and grouping of the same operator do not matter |
| Distributive | A ∧ (B ∨ C) = (A ∧ B) ∨ (A ∧ C), A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C) |
| Absorption | A ∨ (A ∧ B) = A, A ∧ (A ∨ B) = A |
Note that the second distributive law (OR distributes over AND) has no counterpart in ordinary arithmetic, which makes it easy to forget.
11. Worked examples
Example 1: Verifying an equivalence with a truth table
Question: Show that A ⊕ B = (A ∨ B) ∧ ¬(A ∧ B).
| A | B | A ∨ B | A ∧ B | ¬(A ∧ B) | (A ∨ B) ∧ ¬(A ∧ B) | A ⊕ B |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 | 0 |
The last two columns match on all four rows, so the expressions are equivalent. Reading it in words: XOR is “at least one is 1” AND “not both are 1”.
Example 2: Sets and complements
Question: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, A = the multiples of 2 in U, and B = the multiples of 3 in U. Find (A ∪ B)ᶜ, and confirm that it equals Aᶜ ∩ Bᶜ.
- A = {2, 4, 6, 8, 10}, B = {3, 6, 9}
- A ∪ B = {2, 3, 4, 6, 8, 9, 10}
- (A ∪ B)ᶜ = {1, 5, 7}
- Aᶜ = {1, 3, 5, 7, 9}, Bᶜ = {1, 2, 4, 5, 7, 8, 10}
- Aᶜ ∩ Bᶜ = {1, 5, 7}
Both give {1, 5, 7}, as De Morgan’s law predicts. Check by counting: |A ∪ B| = 5 + 3 − |{6}| = 7, and 10 − 7 = 3 elements remain outside.
Example 3: Negating an implication
Question: Simplify ¬(A → B).
- A → B = ¬A ∨ B
- ¬(¬A ∨ B) = ¬¬A ∧ ¬B (De Morgan)
- = A ∧ ¬B (double negation)
So “if A then B” fails exactly when “A and not B”. In set terms, A ⊆ B fails exactly when A ∩ Bᶜ is not empty.
12. Common traps
- Half-applied De Morgan. Negating the terms without swapping ∧/∨ (or swapping without negating) gives a wrong answer.
- Scope of negation. ¬A ∧ B and ¬(A ∧ B) are different expressions.
- Treating OR as exclusive. OR includes the case where both are 1; only XOR excludes it.
- Ignoring precedence. Reading A ∨ B ∧ C from left to right as (A ∨ B) ∧ C is wrong under the usual convention.
- Confusing an implication with its converse. A → B does not mean B → A.
- “Neither” vs. “not both”. “Neither A nor B” is (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ. “Not both” is (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ.
- Forgetting the second distributive law. A ∨ (B ∧ C) = (A ∨ B) ∧ (A ∨ C).
- Counting errors. Forgetting to subtract the intersection, or forgetting the region outside both sets.
- Missing truth-table rows. n variables always need 2ⁿ rows.
13. Practice questions (Motitory originals)
Motitory original / not an official IPA past question. All four questions below were written independently by Motitory for practice.
Question 1 — Complement of a set expression
For sets A and B in a universal set U, which expression is equal to (A ∩ Bᶜ)ᶜ?
- (a) Aᶜ ∩ B
- (b) A ∪ Bᶜ
- (c) Aᶜ ∪ Bᶜ
- (d) Aᶜ ∪ B
Answer: (d)
Worked solution: By De Morgan, (A ∩ Bᶜ)ᶜ = Aᶜ ∪ (Bᶜ)ᶜ. Since the complement of a complement is the original set, (Bᶜ)ᶜ = B, giving Aᶜ ∪ B. In Venn terms, A ∩ Bᶜ is the “A only” region, so its complement is every other region: “B only”, “both”, and “neither”, which is exactly Aᶜ ∪ B.
Explanation of each option:
- (a) Wrong. The terms were negated but ∩ was not changed to ∪. Counterexample: an element in both A and B lies in Aᶜ ∪ B but not in Aᶜ ∩ B.
- (b) Wrong. The operator was swapped but the terms were not negated. Counterexample: an element in A only is not in the correct answer, yet it is in A ∪ Bᶜ.
- (c) Wrong. Bᶜ was left as it is instead of becoming B (double complement). Counterexample: an element in A only is in Aᶜ ∪ Bᶜ (because it is in Bᶜ), but it is not in the correct answer.
- (d) Correct. Both terms are negated and the operator is swapped.
Question 2 — An expression that behaves like XOR
Logical variables A and B take the value 0 or 1. Which expression has the value 1 exactly when A and B have different values?
- (a) A ∨ B
- (b) ¬(A ∧ B)
- (c) (A ∧ ¬B) ∨ (¬A ∧ B)
- (d) (A ∨ ¬B) ∧ (¬A ∨ B)
Answer: (c)
Worked solution: “Different values” means (A, B) = (1, 0) or (0, 1). A ∧ ¬B is 1 only for (1, 0), and ¬A ∧ B is 1 only for (0, 1). Their OR is 1 for exactly those two rows, which is the definition of A ⊕ B.
| A | B | (a) | (b) | (c) | (d) |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 0 | 1 |
Explanation of each option:
- (a) Wrong. OR is inclusive, so it is also 1 when (A, B) = (1, 1), where the values are the same.
- (b) Wrong. This is NAND, which is also 1 when (A, B) = (0, 0).
- (c) Correct. It is 1 only for (1, 0) and (0, 1).
- (d) Wrong. This is 1 when the values are the same, i.e., the negation of XOR (equivalence). It is a trap for anyone who mixes up which parts are negated.
Question 3 — Precedence
Assume the precedence NOT > AND > OR. For which input (A, B, C) does X = ¬A ∨ B ∧ C have the value 0?
- (a) (A, B, C) = (1, 1, 0)
- (b) (A, B, C) = (0, 0, 0)
- (c) (A, B, C) = (0, 1, 0)
- (d) (A, B, C) = (1, 1, 1)
Answer: (a)
Worked solution: With the given precedence, X = (¬A) ∨ (B ∧ C). X is 0 only when both ¬A = 0 and B ∧ C = 0, that is, when A = 1 and B ∧ C = 0. For (1, 1, 0): ¬A = 0 and B ∧ C = 1 ∧ 0 = 0, so X = 0.
Explanation of each option:
- (a) Correct. Both parts are 0, so X = 0.
- (b) Wrong. A = 0 makes ¬A = 1, so X = 1. If you read the expression left to right as (¬A ∨ B) ∧ C, you would get 0 and might choose this option by mistake.
- (c) Wrong. Again A = 0 makes ¬A = 1, so X = 1. The left-to-right reading also gives 0 here, which shows why that reading is unreliable.
- (d) Wrong. ¬A = 0, but B ∧ C = 1, so X = 1.
Question 4 — Counting with a complement
A universal set U has 50 elements. For subsets A and B, |A| = 30, |B| = 25, and |Aᶜ ∩ Bᶜ| = 5. How many elements does A ∩ B have?
- (a) 5
- (b) 10
- (c) 25
- (d) 45
Answer: (b)
Worked solution: By De Morgan, Aᶜ ∩ Bᶜ = (A ∪ B)ᶜ, so |A ∪ B| = 50 − 5 = 45. Then |A ∩ B| = |A| + |B| − |A ∪ B| = 30 + 25 − 45 = 10.
Explanation of each option:
- (a) Wrong. This is 30 + 25 − 50, which assumes A ∪ B = U and ignores the 5 elements that are in neither set.
- (b) Correct.
- (c) Wrong. |A ∩ B| = 25 would require B ⊆ A, but then |A ∪ B| = |A| = 30, which contradicts |A ∪ B| = 45.
- (d) Wrong. 45 is |A ∪ B|, an intermediate value, not the intersection.
14. Final self-check and review plan
Check that you can do each of the following without looking back:
- Shade (A ∪ B)ᶜ and (A ∩ B)ᶜ on a two-set Venn diagram and state the difference.
- Write the truth tables of AND, OR, XOR, NAND, NOR, and A → B from memory.
- Add parentheses to A ∨ B ∧ ¬C using the usual precedence.
- Apply De Morgan’s laws in both set form and propositional form.
- Prove or disprove an equivalence with a truth table, giving a counterexample row when it fails.
Spaced-review suggestion: re-solve the four practice questions without notes after about 1 day, 3 days, and 7 days. Keep track of your results on your own if you wish; this article does not collect any learner data.
15. Sources
- IPA, Applied Information Technology Engineer Examination (Level 3) Syllabus Ver.7.2 (応用情報技術者試験（レベル3）シラバス Ver.7.2), used only to define the scope of this installment: https://www.ipa.go.jp/shiken/syllabus/omgdg50000005kq5-att/syllabus_ap_ver7_2.pdf (checked 2026-10-20)
The explanations, examples, and practice questions in this article were independently written by Motitory. They are not taken from IPA past questions or third-party explanations.