Question

(a) Find the resolvant of \((p \vee q)\) and \((\neg p \vee r)\) on \(p\). (b) Find the resolvant of \((p \vee q \vee r \vee s)\) and \((\neg p \vee \neg q \vee t)\) on \(p\). (c) Find the resolvant of \((p \vee q)\) and \(\neg p\) on \(p\). (d) Find the resolvant of \((p)\) and \((\neg p)\) on \(p\). (e) Which resolvant above from parts (a) through (d) is a tautology? Which is tautologically false?

Short answer

The resolvant from part (d) is tautologically false. No tautology exists among them.

Step-by-step solution

Understanding Resolution

Resolution is a rule in propositional logic for finding conclusions from two premises. If you have two clauses, one containing a literal and the other containing its negation, the resolution rule allows you to produce a new clause excluding the literal and its negation but including the rest of the literals from both clauses.

Resolving (p ∨ q) and (¬p ∨ r) on p

For the clauses \(p \vee q\) and \(eg p \vee r\), resolve on \(p\):- The literal \(p\) in the first clause is positive.- The literal \(eg p\) in the second clause is negative.- The resolvent of these is found by taking the remaining literals \(q\) and \(r\), resulting in the clause \(q \vee r\).

Resolving (p ∨ q ∨ r ∨ s) and (¬p ∨ ¬q ∨ t) on p

For the clauses \(p \vee q \vee r \vee s\) and \(eg p \vee eg q \vee t\), resolve on \(p\):- Remove \(p\) from the first clause and \(eg p\) from the second.- Merge the remaining literals: \(q \vee r \vee s \vee eg q \vee t\).- By simplifying, we observe that \(q\) and \(eg q\) cancel out to create a tautology, leaving us with \(r \vee s \vee t\).

Resolving (p ∨ q) and ¬p on p

For the clauses \(p \vee q\) and \(eg p\), resolve on \(p\):- Literal \(p\) is positive in the first clause, and \(eg p\) is negative in the second.- The resolvent is the remaining literal \(q\), as there are no additional literals in the second clause.

Resolving (p) and (¬p) on p

For the clauses \(p\) and \(eg p\), resolve on \(p\):- Literal \(p\) and \(eg p\) are direct opposites.- The resolution step results in an empty clause, indicating a contradiction, often called tautologically false.

Analyzing Results

Review each resolved clause to determine if it is a tautology or requires no further computation.- From part (a), \(q \vee r\) is not a tautology.- From part (b), no redundant literals appear, resulting in \(r \vee s \vee t\), not a tautology.- From part (c), the clause \(q\) is not a tautology.- From part (d), the resulting empty clause is tautologically false.

Key concepts

Tautology in Logic

In logic, a **tautology** refers to a formula or statement that is always true, regardless of the truth values of its components. This concept is essential because knowing whether an expression is tautological can simplify logical reasoning or proofs significantly.

The defining characteristic of a tautology is its unconditional truth. Consider the expression ``` (p ∨ ¬p) ``` For any value of the proposition **p**—whether true or false—this expression will invariably yield a truth value of true. This is because if **p** is true, then **p** within the disjunction ( ``` ∨ ``` ) will be true, thus validating the entire statement. If **p** is false, then ``` ¬p ``` , i.e., the negation, will be true, again confirming the truth of the complete expression.

Understanding tautologies is crucial when working with propositional logic, as they can help identify clauses that do not require further evaluation. In the exercise above, none of the results from the resolvants were tautologies, indicating that each required further consideration when analyzing logical outcomes.

Contradiction in Logic

A **contradiction** in logic is the opposite of a tautology. It is a statement or formula that is invariably false, regardless of the truth values of its constituent propositions. Understanding contradictions is key to identifying impossible scenarios in logical reasoning.

Consider the expression ``` (p ∧ ¬p) ``` . For any proposition **p**, it is impossible for both **p** and its negation ``` ¬p ``` to be true at the same time. Therefore, this conjunction ( ``` ∧ ``` ) will always be false, representing a tautologically false or logically impossible statement.

In the step-by-step solution provided above, the part (d) resulted in an empty clause after resolution, which is interpreted as a contradiction. This means that the simultaneous truth of **p** and ``` ¬p ``` is impossible, confirming that the resolved clause cannot be true under any circumstances.

Recognizing contradictions can be particularly useful in proofs, especially in indirect proofs or when confirming inconsistencies in logic-based problems.

Literal in Propositional Logic

In the realm of propositional logic, a **literal** is the most basic component of a clause or expression. It can be a straightforward proposition (like **p**) or the negation of a proposition (like ``` ¬p ``` ). Understanding literals is fundamental to dealing with propositional logic because they form the building blocks of more complex logical expressions.

When dealing with resolution in propositional logic, such as in the exercises provided, it is essential to accurately identify and handle literals. Each resolution step involves choosing a literal that appears in its original form in one clause and in its negated form in another. The theorem of resolution then allows you to eliminate these literals and combine the remaining ones to form a new clause.

For instance, when resolving clauses such as ``` (p ∨ q) ``` and ``` (¬p ∨ r) ``` , the literal **p** is handled by removing both **p** and ``` ¬p ``` to produce the resolvent ``` q ∨ r ``` . This simplification plays a critical role in logic-based problem-solving, allowing one to simplify complex expressions and draw conclusions efficiently.