1What is a propositional variable?
A symbol that represents a proposition with a truth value true or false
2What is a proposition?
A declarative statement that is either true or false but not both
3What does it mean for a proposition to have a truth value?
It can be evaluated as either true or false
4What are the standard logical connectives in propositional logic?
Negation, conjunction, disjunction, implication, equivalence ¬, ∧, ∨, →, ↔
5What is the difference between syntax and semantics in propositional logic?
Syntax concerns the form of formulas, semantics concerns their meaning and truth values
6What is a well-formed formula (WFF)?
A syntactically correct expression built according to the rules of propositional logic
7How do you construct a truth table for a propositional formula?
By listing all possible truth value assignments for variables and evaluating the formula
8How many rows does a truth table with n variables have?
2ⁿ rows
9What is the truth table definition of ¬A?
It is true when A is false and false when A is true
10What is the truth table definition of A ∧ B?
True only when both A and B are true
11What is the truth table definition of A ∨ B?
True when at least one of A or B is true
12What is the truth table definition of A → B?
False only when A is true and B is false
13What is the truth table definition of A ↔ B?
True when A and B have the same truth value
14In which cases is an implication false?
When the antecedent is true and the consequent is false
15How is impication defined?
Implication is defined as ¬A ∨ B
16What is a tautology?
A formula that is true under all truth assignments
17What is a contradiction?
A formula that is false under all truth assignments
18What is a satisfiable formula?
A formula that is true under at least one truth assignment
19What is an unsatisfiable formula?
A formula that is false under all truth assignments
20What does it mean for a formula to be valid?
It is true in all interpretations
21Can a formula be both satisfiable and a tautology?
Yes, every tautology is satisfiable
22Can a formula be satisfiable but not a tautology?
Yes, if it is true under some but not all assignments
23What does it mean for two formulas to be logically equivalent?
They have the same truth value under all interpretations
24How can logical equivalence be shown using truth tables?
By showing identical truth table columns for both formulas
25What does the symbol ≡ represent?
Logical equivalence
26Are logically equivalent formulas guaranteed to have the same truth table?
Yes
27Is logical equivalence the same as syntactic equality?
No
28What is the commutative law for ∧ and ∨?
A ∧ B ≡ B ∧ A and A ∨ B ≡ B ∨ A
29What is the associative law for ∧ and ∨?
(A ∧ B) ∧ C ≡ A ∧ (B ∧ C) and similarly for ∨
30What is the distributive law involving ∧ and ∨?
A ∧ (B ∨ C) ≡ (A ∧ B) ∨ (A ∧ C)
31What is the identity law in propositional logic?
A ∧ true ≡ A and A ∨ false ≡ A
32What is the domination law?
A ∨ true ≡ true and A ∧ false ≡ false
33What is the idempotent law?
A ∧ A ≡ A and A ∨ A ≡ A
34What is the double negation law?
¬¬A ≡ A
35What are De Morgan’s laws?
¬(A ∧ B) ≡ ¬A ∨ ¬B and ¬(A ∨ B) ≡ ¬A ∧ ¬B
36How do De Morgan’s laws apply to negated conjunctions?
They transform them into disjunctions of negations
37How do De Morgan’s laws apply to negated disjunctions?
They transform them into conjunctions of negations
38How can implication be rewritten using ¬ and ∨?
A → B ≡ ¬A ∨ B
39How can equivalence be rewritten using implications?
A ↔ B ≡ (A → B) ∧ (B → A)
40What is the contrapositive of an implication?
¬B → ¬A
41Is an implication logically equivalent to its contrapositive?
Yes
42What is the converse of an implication?
B → A
43Is an implication logically equivalent to its converse?
No
44What is the inverse of an implication?
¬A → ¬B
45How do you simplify a propositional formula using logical laws?
By applying equivalences and identities step by step
46What steps are typically used when simplifying complex formulas?
Remove implications, push negations inward, apply equivalence laws
47How do you remove implications from a formula?
Replace A → B with ¬A ∨ B
48How do you remove equivalences from a formula?
Replace A ↔ B with (A → B) ∧ (B → A)
49How do you push negations inward?
By applying De Morgan’s laws and double negation
50How do you identify redundant parts of a formula?
By checking logical equivalence
51What does it mean for a formula B to be a logical consequence of formula A?
B is true in every interpretation where A is true
52What does the notation A ⊨ B mean?
B is a logical consequence of A
53How can logical consequence be checked using truth tables?
By verifying that there is no row where A is true and B is false
54Can a formula have multiple logical consequences?
Yes
55Can a contradiction have logical consequences?
Yes, it logically implies every formula
56Can a tautology be a logical consequence of any formula?
Yes
57Can A ∧ B logically imply A?
Yes
58Can A logically imply A ∨ B?
Yes
59Does A ∧ B imply B ∧ A?
Yes
60Does A → B imply ¬B → ¬A?
Yes
61Is A ∨ ¬A always true?
Yes
62Is A ∧ ¬A always false?
Yes
63What is a predicate?
A function that assigns truth values to objects
64What is the difference between a propositional variable and a predicate?
A predicate depends on variables, a proposition does not
65What does a unary predicate represent?
A property of a single object
66What does a binary predicate represent?
A relation between two objects
67What is the universal quantifier?
A quantifier stating that a property holds for all elements
68What is the existential quantifier?
A quantifier stating that a property holds for at least one element
69What symbols are used for ∀ and ∃?
Universal and existential quantifiers
70What is a domain (universe of discourse)?
The set of objects over which variables range
71Why is the domain important when interpreting predicates?
Because it determines which objects are quantified over
72Can the same predicate formula have different truth values under different domains?
Yes
73What is an interpretation of a predicate formula?
An assignment of meaning to predicates and variables
74What is a bound variable?
A variable that is quantified by ∀ or ∃
75What is a free variable?
A variable not bound by a quantifier
76Is a formula with free variables a proposition?
No
77When is a predicate formula considered closed?
When it has no free variables
78Can a variable be both free and bound in the same formula?
Yes, in different occurrences
79What does ∀x P(x) mean in words?
P holds for every element in the domain
80What does ∃x P(x) mean in words?
There exists at least one element for which P holds
81Does ∀x P(x) imply ∃x P(x)?
Yes, if the domain is non-empty
82Does ∃x P(x) imply ∀x P(x)?
No
83Can ∀x P(x) be true if the domain is empty?
Yes, by convention
84Can ∃x P(x) be true if the domain is empty?
No
85What is the negation of ∀x P(x)?
∃x ¬P(x)
86What is the negation of ∃x P(x)?
∀x ¬P(x)
87How does negation interact with quantifiers?
It switches ∀ and ∃ and negates the predicate
88How do De Morgan’s laws apply to quantified formulas?
They move negation across quantifiers
89How do you negate nested quantifiers?
By reversing each quantifier and negating the inner formula
90What is the negation of ∀x ∃y P(x, y)?
∃x ∀y ¬P(x, y)
91What is the negation of ∃x ∀y P(x, y)?
∀x ∃y ¬P(x, y)
92What does it mean for a predicate formula to be a logical consequence of another?
It holds in every interpretation where the first formula holds
93Does ∀x P(x) logically imply P(a) for a specific element a?
Yes
94Does P(a) logically imply ∃x P(x)?
Yes
95Does ¬∃x P(x) imply ∀x ¬P(x)?
Yes
96Does ¬∀x P(x) imply ∃x ¬P(x)?
Yes
97Which formulas follow from ∀x P(x)?
Any instance P(a)
98Which formulas follow from ∃x P(x)?
No specific instance without additional information
99Which formulas follow from ¬∃x P(x)?
∀x ¬P(x)
100Which formulas follow from ¬∀x P(x)?
∃x ¬P(x)
101Can both ∃x P(x) and ∀x ¬P(x) be true at the same time?
No
102Can both ∀x P(x) and ∃x ¬P(x) be true at the same time?
No
103Is ¬∃x P(x) the same as ∃x ¬P(x)?
No
104Is ¬∀x P(x) the same as ∀x ¬P(x)?
No
105Does switching the order of quantifiers change meaning?
Yes, in general
106Is ∀x ∃y P(x, y) equivalent to ∃y ∀x P(x, y)?
No
107Can a statement be true for all elements but false for some specific symbol?
No