Logic and Computation Flashcards
What is a set?
An unordered collection of distinct elements or members.
What notation is used to define a set?
Curly braces { }, e.g., A = {1, 2, 3, 4, 5}.
What does the symbol ∈ mean in set notation?
“Element of,” meaning an item is a member of a set.
What is the cardinality of a set?
The number of elements in a set, denoted |A| or #A.
What is a subset (⊆) and a proper subset (⊂)?
A subset includes all elements of another set, while a proper subset includes some but not all.
What is the union (∪) of two sets?
A set containing all elements that are in either set or both.
What is the intersection (∩) of two sets?
A set containing only elements common to both sets.
What is the empty set?
A set with no elements, denoted ∅ or { }
Define the sets ℕ, ℤ, ℚ, ℝ, ℂ, ℙ, and ∅.
ℕ: Natural numbers, ℤ: Integers, ℚ: Rational numbers, ℝ: Real numbers, ℂ: Complex numbers, ℙ: Prime numbers, ∅: Empty set.
What is logic?
The science of valid reasoning, involving constructing valid arguments.
What is propositional logic?
Logic dealing with propositions and logical connectives.
Define Boolean Logic.
A type of algebra with only two values: true (1) or false (0).
What is predicate logic?
Logic with predicates, allowing more complex statements about objects and properties.
What is a simple proposition?
A statement expressing a single, complete thought that cannot be broken down.
Define a compound proposition.
A statement combining two or more simple propositions with logical connectives.
What does the AND (∧) connective mean?
It is true only when both propositions are true.
Define the OR (∨) connective.
It is true when at least one proposition is true.
What is NOT (¬) in logical terms?
A connective that negates the truth value of a proposition.
Explain XOR (⊕).
It is true when exactly one of the propositions is true.
What is the IMPLIES (→) operator?
It is false only when the first proposition is true and the second is false.
Define a tautology.
A compound proposition that is always true.
What is a contradiction?
A compound proposition that is always false.
What does antecedent mean in a conditional statement?
The “if” part of an “if-then” statement.
Define consequent in a conditional statement.
The “then” part of an “if-then” statement.
What is a vacuous truth?
A statement that is true because its antecedent is false.
What are critical rows in a truth table?
Rows where premises are true, and the conclusion is false, showing invalidity.
What is Modus Ponens?
If P → Q and P, then Q.
What is Modus Tollens?
If P → Q and ¬Q, then ¬P.
What is a generalisation rule in inference?
From P, infer P ∨ Q.
Define the conjunction rule in inference.
From P and Q, infer P ∧ Q.
Explain elimination in propositional logic.
From P ∨ Q and ¬Q, infer P.
What is a contradiction rule?
From ¬P → c, infer P.
What is logical equivalence?
When two statements have the same truth value.
Define the existential quantifier.
“There exists” (∃), meaning at least one member of the set.
Define the universal quantifier.
“For all” (∀), meaning it applies to all members of the set.
What is a universal conditional statement?
A statement applying universally in the form “if P(x) then Q(x).”
What is the contrapositive of a statement?
Negating and switching the parts of an “if-then” statement.
Example: For the statement “If it is raining, then the ground is wet,” the contrapositive is “If the ground is not wet, then it is not raining.”
Define inverse in logic.
.
Negating both parts of an “if-then” statement
Example: For the statement “If it is raining, then the ground is wet,” the inverse is “If it is not raining, then the ground is not wet.”
Define converse in logic.
Switching the parts of an “if-then” statement.
Example: For the statement “If it is raining, then the ground is wet,” the converse is “If the ground is wet, then it is raining.”
What is the logical equivalence theorem for UCS?
The original statement is equivalent to its contrapositive; inverse is equivalent to converse.
