Theory of Computation: Question Set – 05

Theory of Computation: Question Set – 05

What is a proposition?

A proposition is a statement that is either true or false, but not both. It is a basic unit of meaning in logic and is used as the basis for logical reasoning.

What is a logical connective?

A logical connective is a word or symbol that is used to combine propositions into a larger proposition. Examples of logical connectives include “and,” “or,” “not,” “implies,” and “if and only if.”

What is the Law of Excluded Middle?

The Law of Excluded Middle is a fundamental principle of logic that states that every proposition is either true or false. There is no middle ground or third option.

What is a tautology?

A tautology is a proposition that is always true, regardless of the truth values of its component propositions. For example, the proposition “either it is raining or it is not raining” is a tautology.

What is a contradiction?

A contradiction is a proposition that is always false, regardless of the truth values of its component propositions. For example, the proposition “it is both raining and not raining” is a contradiction.

What is propositional logic?

Propositional logic is a branch of logic that deals with propositions and their logical relationships. It is concerned with the logical connectives that are used to combine propositions into more complex propositions.

What is predicate logic?

Predicate logic is a branch of logic that extends propositional logic by adding quantifiers and predicates to the language. It is concerned with the logical relationships between predicates and their subjects.

What is a quantifier?

A quantifier is a word or symbol that is used to indicate the scope of a variable in a logical expression. The two most common quantifiers are “forall” and “exists,” which indicate universal and existential quantification, respectively.

What is a contingency?

A contingency is a proposition that can be either true or false, depending on the truth values of its variables.

What is the negation of a proposition?

The negation of a proposition is a statement that is true when the original statement is false, and false when the original statement is true.

What is the conjunction of two propositions?

The conjunction of two propositions is a proposition that is true only when both of the original propositions are true.

What is the disjunction of two propositions?

The disjunction of two propositions is a proposition that is true when either one or both of the original propositions are true.