Logic and Computation

Question 1

What is a set?

Answer 1

An unordered collection of distinct elements or members.

Question 2

What notation is used to define a set?

Answer 2

Curly braces { }, e.g., A = {1, 2, 3, 4, 5}.

Question 3

What does the symbol ∈ mean in set notation?

Answer 3

“Element of,” meaning an item is a member of a set.

Question 4

What is the cardinality of a set?

Answer 4

The number of elements in a set, denoted |A| or #A.

Question 5

What is a subset (⊆) and a proper subset (⊂)?

Answer 5

A subset includes all elements of another set, while a proper subset includes some but not all.

Question 6

What is the union (∪) of two sets?

Answer 6

A set containing all elements that are in either set or both.

Question 7

What is the intersection (∩) of two sets?

Answer 7

A set containing only elements common to both sets.

Question 8

What is the empty set?

Answer 8

A set with no elements, denoted ∅ or { }

Question 9

Define the sets ℕ, ℤ, ℚ, ℝ, ℂ, ℙ, and ∅.

Answer 9

ℕ: Natural numbers, ℤ: Integers, ℚ: Rational numbers, ℝ: Real numbers, ℂ: Complex numbers, ℙ: Prime numbers, ∅: Empty set.

Question 10

What is logic?

Answer 10

The science of valid reasoning, involving constructing valid arguments.

Question 11

What is propositional logic?

Answer 11

Logic dealing with propositions and logical connectives.

Question 12

Define Boolean Logic.

Answer 12

A type of algebra with only two values: true (1) or false (0).

Question 13

What is predicate logic?

Answer 13

Logic with predicates, allowing more complex statements about objects and properties.

Question 14

What is a simple proposition?

Answer 14

A statement expressing a single, complete thought that cannot be broken down.

Question 15

Define a compound proposition.

Answer 15

A statement combining two or more simple propositions with logical connectives.

Question 16

What does the AND (∧) connective mean?

Answer 16

It is true only when both propositions are true.

Question 17

Define the OR (∨) connective.

Answer 17

It is true when at least one proposition is true.

Question 18

What is NOT (¬) in logical terms?

Answer 18

A connective that negates the truth value of a proposition.

Question 19

Explain XOR (⊕).

Answer 19

It is true when exactly one of the propositions is true.

Question 20

What is the IMPLIES (→) operator?

Answer 20

It is false only when the first proposition is true and the second is false.

Question 21

Define a tautology.

Answer 21

A compound proposition that is always true.

Question 22

What is a contradiction?

Answer 22

A compound proposition that is always false.

Question 23

What does antecedent mean in a conditional statement?

Answer 23

The “if” part of an “if-then” statement.

Question 24

Define consequent in a conditional statement.

Answer 24

The “then” part of an “if-then” statement.

Question 25

What is a vacuous truth?

Answer 25

A statement that is true because its antecedent is false.

Question 26

What are critical rows in a truth table?

Answer 26

Rows where premises are true, and the conclusion is false, showing invalidity.

Question 27

What is Modus Ponens?

Answer 27

If P → Q and P, then Q.

Question 28

What is Modus Tollens?

Answer 28

If P → Q and ¬Q, then ¬P.

Question 29

What is a generalisation rule in inference?

Answer 29

From P, infer P ∨ Q.

Question 30

Define the conjunction rule in inference.

Answer 30

From P and Q, infer P ∧ Q.

Question 31

Explain elimination in propositional logic.

Answer 31

From P ∨ Q and ¬Q, infer P.

Question 32

What is a contradiction rule?

Answer 32

From ¬P → c, infer P.

Question 33

What is logical equivalence?

Answer 33

When two statements have the same truth value.

Question 34

Define the existential quantifier.

Answer 34

“There exists” (∃), meaning at least one member of the set.

Question 35

Define the universal quantifier.

Answer 35

“For all” (∀), meaning it applies to all members of the set.

Question 36

What is a universal conditional statement?

Answer 36

A statement applying universally in the form “if P(x) then Q(x).”

Question 37

What is the contrapositive of a statement?

Answer 37

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.”

Question 38

Define inverse in logic. .

Answer 38

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.”

Question 39

Define converse in logic.

Answer 39

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.”

Question 40

What is the logical equivalence theorem for UCS?

Answer 40

The original statement is equivalent to its contrapositive; inverse is equivalent to converse.