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

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.