PadhaikoAll subjects

Propositional Logic, Rules of Inference & Predicate Logic

Theory of Computation (ENCT 203)

Open in the Padhaiko app

1.2 Propositional Logic (Book 1.3.1)

Logic is the formal discipline of reasoning that distinguishes valid arguments from invalid ones. It is divided into two principal branches:

  1. Propositional Logic (Logic of Sentences): Studies ways of combining or modifying entire declarative statements using logical connectives, and the truth-functional relationships that arise from them.
  2. Predicate Logic (Logic of Objects): Extends propositional logic to statements involving variables, properties (predicates), and quantifiers.
Definition

Proposition and Propositional Variables

A proposition is a declarative statement (sentence) that is either true () or false (), but not both.

Propositional variables are lowercase letters () used to denote propositions—for example, : "Today is Tuesday."

Propositions are classified as:

  1. Atomic Proposition (Primary / Primitive): A simple proposition that cannot be subdivided into smaller propositions.
  2. Compound Proposition (Molecular / Complete): A proposition formed by combining two or more propositions using logical operators (connectives) or by negating a proposition.
Logical Connectives (Operators)
ConnectiveNotationRead As / Meaning
Negation or Not ("It is not the case that ")
Conjunction and
Disjunction or (inclusive OR)
Implication (Conditional)If then ( implies )
Bi-implication (Biconditional) or if and only if ()

Truth Tables of Fundamental Connectives

Definition

Negation, Conjunction, Disjunction, Implication, and Bi-implication

  1. Negation (): For a proposition , its negation is read "it is not the case that " and reverses the truth value of .
    • Example: : "Today is Friday." : "It is not the case that today is Friday."
  2. Conjunction (): Read " and ". It is true when both and are true, and false otherwise.
    • Example: : "It is Friday.", : "It is raining." : "It is Friday and it is raining."
  3. Disjunction (, Inclusive OR): Read " or ". It is true when at least one of or is true, and false only when both and are false.
    • Example: : "She has a pen.", : "She has a pencil." : "She has a pen or a pencil."
  4. Implication / Conditional (): Read "if then " or " implies ". Here is the hypothesis (premise or sufficient condition) and is the conclusion (consequence or necessary condition). The statement is false only when is true and is false, and is true in all other cases.
  5. Bi-implication / Biconditional (): Read " if and only if " (), or " is a necessary and sufficient condition for ". It is equivalent to , and is true when and have the same truth value (both true or both false) and false otherwise.
Master Truth Table for Basic Connectives

Converse, Contrapositive, and Inverse

Definition

Converse, Contrapositive, and Inverse of p → q

Given a conditional statement :

An implication and its contrapositive are logically equivalent (), and likewise the converse and inverse are logically equivalent:

Truth Table Showing Equivalence of p → q and ¬q → ¬p

Tautology, Contradiction, Contingency, and Logical Equivalence

Definition

Tautology, Contradiction, Contingency, and Logical Equivalence

  1. Tautology: A compound proposition that is always true for every possible assignment of truth values to its propositional variables. Example: .
  2. Contradiction (Fallacy): A compound proposition that is always false for every possible assignment of truth values. Example: . (The negation of a tautology is a contradiction, and the negation of a contradiction is a tautology.)
  3. Contingency: A compound proposition that is neither a tautology nor a contradiction (true in some cases and false in others). Example: .
  4. Logical Equivalence ( or ): Two compound propositions and are logically equivalent if they have the exact same truth values in all possible cases (equivalently, is a tautology).

For example, De Morgan's Law is verified by comparing their truth tables:

Verification of De Morgan's Law: ¬(p ∨ q) ≡ ¬p ∧ ¬q

Worked Out Examples: Propositional Logic & Translation

Example 1.4

1.4

State the converse, contrapositive, and inverse of the following conditional statement: "If it is sunny then I go to beach."

Defining propositional variables: Let : "It is sunny." and : "I go to beach." The given statement is .

Forming converse, contrapositive, and inverse:

  • Converse (): "If I go to beach then it is sunny."
  • Contrapositive (): "If I do not go to beach then it is not sunny."
  • Inverse (): "If it is not sunny then I do not go to beach."
Answer:

Converse: "If I go to beach then it is sunny." Contrapositive: "If I do not go to beach then it is not sunny." Inverse: "If it is not sunny then I do not go to beach."

Example 1.5

1.5

State the converse, contrapositive, and inverse of the following conditional statement: "The home team wins whenever it is raining."

Rewriting in standard "If then " form: The statement has the form " whenever ", which means . Let : "It is raining." and : "The home team wins." Standard form (): "If it is raining then the home team wins."

Forming converse, contrapositive, and inverse:

  • Converse (): "If the home team wins then it is raining."
  • Contrapositive (): "If the home team does not win then it is not raining."
  • Inverse (): "If it is not raining then the home team does not win."
Answer:

Converse: "If the home team wins then it is raining." Contrapositive: "If the home team does not win then it is not raining." Inverse: "If it is not raining then the home team does not win."

Example 1.6

1.6

State the converse, contrapositive, and inverse of the following conditional statement: "A positive integer is a prime only if it has no divisors other than and itself."

Rewriting in standard "If then " form: The statement has the form " only if ", which means . Let : "A positive integer is a prime." and : "It has no divisors other than and itself." Standard form (): "If a positive integer is a prime then it has no divisors other than and itself."

Forming converse, contrapositive, and inverse:

  • Converse (): "If a positive integer has no divisors other than and itself then it is a prime number."
  • Contrapositive (): "If a positive integer has divisors other than and itself then it is not a prime number."
  • Inverse (): "If a positive integer is not a prime then it has divisors other than and itself."
Answer:

Converse: "If a positive integer has no divisors other than and itself then it is a prime number." Contrapositive: "If a positive integer has divisors other than and itself then it is not a prime number." Inverse: "If a positive integer is not a prime then it has divisors other than and itself."

Example 1.7

1.7

State the converse, contrapositive, and inverse of the following conditional statement: "If flood destroys my house or the fire destroys my house then my insurance company will pay me."

Symbolic representation: Let : "Flood destroys my house", : "Fire destroys my house", and : "My insurance company will pay me." The given statement is .

Forming converse, contrapositive, and inverse using De Morgan's Law:

  • Converse (): "If my insurance company will pay me then the flood destroys my house or the fire destroys my house."
  • Contrapositive (): "If my insurance company won't pay me then the flood does not destroy my house and the fire does not destroy my house."
  • Inverse (): "If the flood does not destroy my house and the fire does not destroy my house then my insurance company will not pay me."
Answer:

Converse: . Contrapositive: . Inverse: .

Example 1.8

1.8

Show that the proposition is a tautology.

Constructing the 8-row truth table: For three variables , there are truth assignments:

Truth Table for ((p ∨ q) ∧ (p → r) ∧ (q → r)) → r

Inspecting the final column: Every entry in the last column is (true), regardless of the truth values of .

Answer:

Since the final column is in all possible cases, is a tautology.

Example 1.9

1.9

Translate into propositional logic: "You can access the internet from the campus if and only if you are a computer science major or you are not a freshman."

Defining atomic propositions:

  • : "You can access the internet from the campus."
  • : "You are a computer science major."
  • : "You are a freshman."

Combining with connectives: "You are a computer science major or you are not a freshman" is . Joining with via "if and only if" () gives:

Answer:
Example 1.10

1.10

Translate into propositional logic: "The automated reply cannot be sent when the file system is full."

Identifying hypothesis and conclusion: Let : "The file system is full." and : "The automated reply can be sent." The sentence has the form " when ", i.e., "If the file system is full, then the automated reply cannot be sent."

Answer:
Example 1.11

1.11

Translate into propositional logic: "School is closed if more than feet of snow falls or the wind chill is below ."

Identifying propositions and connectives: Let : "School is closed", : "More than feet of snow falls", and : "The wind chill is below ." The statement has the form " if ", which is .

Answer:
Example 1.12

1.12

Translate into propositional logic: "Ram is either smart or honest, but Ram is not honest if he is smart."

Translating each clause: Let : "Ram is smart." and : "Ram is honest."

  • "Ram is either smart or honest": .
  • "but" in logic has the same truth-functional meaning as "and" ().
  • "Ram is not honest if he is smart" has the form " if ", which is .

Combining the two clauses with yields:

Answer:
Example 1.13

1.13

Translate into propositional logic: "Ram is smart is necessary and sufficient for Ram to be honest."

Recognizing the biconditional: Let : "Ram is smart." and : "Ram is honest." The phrase " is necessary and sufficient for " means "Ram is smart if and only if he is honest", which is the bi-implication .

Answer:

1.3.2 Predicate Logic

Definition

Predicate (Propositional Function) and Quantifiers

Predicate logic (or predicate calculus) deals with predicates, which are declarative statements containing variables whose truth value depends on the values assigned to those variables.

Consider the statement " is greater than ":

We denote this propositional function by . By itself, is not a proposition, but once a specific value is substituted for (or is bound by a quantifier such as the universal quantifier or the existential quantifier ), becomes a proposition with a definite truth value ( or ).

Example 1.14

1.14

If denotes the statement " is greater than ", what are the truth values of and ?

Evaluating and :

  • Substituting : is the statement " is greater than ", which is true ().
  • Substituting : is the statement " is greater than ", which is false ().
Answer:

is true and is false.

1.3.3 Rules of Inference in Propositional Logic

Definition

Argument, Premises, Conclusion, and Rules of Inference

An argument in propositional logic is a sequence of statements ending with a conclusion:

Rules of inference are fundamental tautological templates used to construct valid step-by-step proofs from given hypotheses.

Standard Rules of Inference in Propositional Logic (Page 28)
Rule of InferenceCorresponding TautologyName
and Modus Ponens
and Modus Tollens
and Hypothetical Syllogism
and Disjunctive Syllogism
Addition
(or ) (or )Simplification
and Conjunction
and Resolution

Worked Out Examples: Proofs Using Rules of Inference

Example 1.15

1.15

Show that the hypotheses:

lead to the conclusion "We will be home by sunset" by using rules of inference.

Assigning propositional variables and hypotheses: Let:

  • : It is sunny this afternoon.
  • : It is colder than yesterday.
  • : We will go for swimming.
  • : We will take a canoe trip.
  • : We will be home by sunset.

Hypotheses: , , , . Conclusion: .

Constructing the formal proof:

Deduction of Conclusion t
No.StatementReason
1Hypothesis
2Simplification on (1)
3Hypothesis
4Modus Tollens on (2) and (3)
5Hypothesis
6Modus Ponens on (4) and (5)
7Hypothesis
8Modus Ponens on (6) and (7)
Answer:

The conclusion ("We will be home by sunset") follows validly by Simplification, Modus Tollens, and two applications of Modus Ponens.

Example 1.16

1.16

Show that the hypotheses:

lead to the conclusion "If I do not finish writing the program then I will get up feeling refreshed" by using rules of inference.

Assigning propositional variables and hypotheses: Let:

  • : You send me an email message.
  • : I will finish writing the program.
  • : I will go to sleep early.
  • : I will get up feeling refreshed.

Hypotheses: , , . Conclusion: .

Constructing the formal proof:

Deduction of Conclusion ¬q → s
No.StatementReason
1Hypothesis
2Contrapositive equivalence of (1)
3Hypothesis
4Hypothetical Syllogism on (2) and (3)
5Hypothesis
6Hypothetical Syllogism on (4) and (5)
Answer:

The conclusion follows validly from the contrapositive of and two applications of Hypothetical Syllogism.

Example 1.17

1.17

Using rules of inference, prove that the hypotheses:

lead to the conclusion "I will take a road trip with my friends."

Assigning propositional variables and hypotheses: Let:

  • : I get my Christmas bonus.
  • : My friends are free.
  • : I will take a road trip with my friends.
  • : My friends find a job after Christmas.

Hypotheses: , , . Conclusion: .

Constructing the formal proof:

Deduction of Conclusion r
No.StatementReason
1Hypothesis
2Hypothesis
3Hypothesis
4Simplification on (3)
5Simplification on (3)
6Modus Ponens on (2) and (5)
7Conjunction on (4) and (6)
8Modus Ponens on (1) and (7)
Answer:

The conclusion ("I will take a road trip with my friends") follows validly by Simplification, Modus Ponens, Conjunction, and Modus Ponens.

Example 1.18

1.18

Using rules of inference, show that the hypotheses:

lead to the conclusion "The Chargers can beat the Jets and the Chargers can beat the Dolphins."

Assigning propositional variables and hypotheses: Let:

  • : The Chargers get a good linebacker.
  • : The Chargers can beat the Broncos.
  • : The Chargers can beat the Jets.
  • : The Chargers can beat the Dolphins.

Hypotheses: , , , . Conclusion: .

Constructing the formal proof:

Deduction of Conclusion r ∧ s
No.StatementReason
1Hypothesis
2Hypothesis
3Hypothetical Syllogism on (1) and (2)
4Hypothesis
5Hypothesis
6Hypothetical Syllogism on (1) and (4)
7Modus Ponens on (5) and (6)
8Modus Ponens on (3) and (5)
9Conjunction on (8) and (7)
Answer:

The conclusion follows validly by Hypothetical Syllogism, Modus Ponens, and Conjunction.

Solutions to Important Questions (Book Page 49)

Example Imp. 10

Imp. 10

Show that the given proposition is a tautology:

Constructing the truth table: We evaluate each sub-formula across all truth assignments for :

Truth Table for Hypothetical Syllogism ((P → Q) ∧ (Q → R)) → (P → R)
Answer:

Since the final column is in every row, is a tautology.

Example Imp. 11

Imp. 11

State the converse, inverse, and contrapositive for the statement: "I will go to swimming only if it is sunny." [2082 Kartik]

Expressing in standard conditional form : The given statement is in the form " only if ", where:

  • : "I will go to swimming."
  • : "It is sunny."

The standard form is: "If I will go to swimming then it is sunny."

Writing the converse, contrapositive, and inverse:

  • Converse (): "If it is sunny then I will go to swimming."
  • Contrapositive (): "If it is not sunny then I will not go to swimming."
  • Inverse (): "If I will not go to swimming then it is not sunny."
Answer:

Converse: "If it is sunny then I will go to swimming." Contrapositive: "If it is not sunny then I will not go to swimming." Inverse: "If I will not go to swimming then it is not sunny."

Exercises

Practice Exercises — Propositional & Predicate Logic

Question 1

Define tautology, contradiction, and contingency with an example of each.

Tautology (definition and truth table): A compound proposition is a tautology if it evaluates to True () under every possible truth assignment of its constituent propositional variables.

  • Example: (Law of Excluded Middle).
  • Truth Table:

Because every entry in the final column is , is a tautology (denoted by or ).

Contradiction (definition and truth table): A compound proposition is a contradiction (or absurdity) if it evaluates to False () under every possible truth assignment of its constituent variables.

  • Example: .
  • Truth Table:

Because every entry in the final column is , is a contradiction (denoted by or ). Note that the negation of any tautology is a contradiction: .

Contingency (definition and truth table): A compound proposition is a contingency if it is neither a tautology nor a contradiction. Its truth value depends entirely on the truth values assigned to its component variables (having at least one and at least one in its truth table).

  • Example: The conditional proposition .
  • Truth Table:

Since the column contains both and , is a contingency.

Answer:
  • Tautology: A compound proposition that is always true (e.g., ).
  • Contradiction: A compound proposition that is always false (e.g., ).
  • Contingency: A compound proposition that is neither always true nor always false (e.g., ).
Question 2

State Modus Ponens, Modus Tollens, Hypothetical Syllogism, and Disjunctive Syllogism with their corresponding tautologies.

Modus Ponens (Law of Detachment):

  • Rule of Inference:
  • Corresponding Tautology: .
  • Meaning: If hypothesis is asserted to be true and the conditional statement is true, the conclusion must necessarily follow.

Modus Tollens (Denying the Consequent):

  • Rule of Inference:
  • Corresponding Tautology: .
  • Meaning: Since the conditional is logically equivalent to its contrapositive , observing that consequent is false forces antecedent to be false.

Hypothetical Syllogism (Transitivity of Implication):

  • Rule of Inference:
  • Corresponding Tautology: .
  • Meaning: Conditional dependencies chain transitively: if truth of guarantees , and truth of guarantees , then guarantees .

Disjunctive Syllogism:

  • Rule of Inference:
  • Corresponding Tautology: (similarly ).
  • Meaning: When at least one of two propositions must hold, eliminating one alternative leaves the remaining alternative true.
Answer:
  • Modus Ponens:
  • Modus Tollens:
  • Hypothetical Syllogism:
  • Disjunctive Syllogism:
Question 3

What is the difference between propositional logic and predicate logic? Give an example of a propositional function .

Key differences between propositional and predicate logic:

  1. Atomic granularity: Propositional logic treats entire declarative statements as indivisible atomic variables (), each assigned a fixed truth value ( or ). Predicate logic looks inside atomic statements, analyzing subjects (objects/variables ) and predicates (properties or relations ).
  2. Expressive power and quantifiers: Propositional logic cannot represent statements asserting properties of "all" or "some" individuals. Predicate logic introduces quantifiers:
    • Universal quantifier (): "for all "
    • Existential quantifier (): "there exists an "
  3. Domain of discourse: Predicate statements are evaluated relative to a specific domain (universe of discourse) over which variables range.

Definition of a propositional function: A propositional function (or predicate) is a statement involving an object variable . It is not a proposition by itself because it does not have a definite truth value until:

  1. A specific value from the domain is assigned to (yielding proposition ), or
  2. The variable is bound by a quantifier ( or ).

Concrete example of : Let the domain of discourse be the set of integers , and consider the propositional function:

  • For : is "", which evaluates to True.
  • For : is "", which evaluates to True.
  • For : is "", which evaluates to False.

When quantified over the domain :

  • is True (witnessed by ).
  • is False (counterexample ).
Answer:

Propositional logic studies whole declarative propositions combined by truth-functional connectives (), whereas predicate logic analyzes internal structure using predicates (properties of variables) and quantifiers (). For example, : "" is a propositional function that becomes true for and false for .

Past exam questions for Theory of Computation

← Sets, Functions & RelationsInduction, Diagonalization & Pigeonhole Principle →