1
$\begingroup$

I have to do the following problem :

Find an expression, which is the and of clauses, equivalent to $( p \lor q) \to r$.

But I don't understand what ''which is the and of clauses'' means.

(I am doing the class in french but the book is in English, so maybe I've seen this expression in french but never translated to English)

$\endgroup$
0
$\begingroup$

A clause is a disjunction of literals, and a literal is an atomic formula or its negation.

So, your exercise asks for a conjunction of clauses, also known as conjunctive normal form, that is logically equivalent to $(p \lor q) \to r$. Using well-known logical equivalences, you get:

\begin{align} (p \lor q) \to r &\equiv \lnot (p \lor q) \lor r &\text{by decomposition of $\to$} \\ &\equiv (\lnot p \land \lnot q) \lor r &\text{by De Morgan law} \\ &\equiv (\lnot p \lor r) \land (\lnot q \lor r) &\text{by distributivity of $\lor$ over $\land$} \end{align}

where $(\lnot p \lor r) \land (\lnot q \lor r)$ is the formula you are looking for because it is a conjunctive normal form (since it is a conjunction of the literals $\lnot p \lor r$ and $\lnot q \lor r$) and it is logically equivalent to $(p \lor q) \to r$ (since it is obtained by substitution of logically equivalent sub-formulas).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.