Propositional Calculus

Question

In a effort to become a better mathematician. I am self-studying Logic using the textbooks "Introduction to mathematical structures and Proofs" by Larry J Gerstein and "A tour though mathematical Logic" by Robert S Wolf.

There are two questions/exercises that I need guidance and hints in order to solve them.

Question 1 : Suppose that $P$ is a Boolean combination of statements $Q_1, Q_2,\ldots, Q_n $ Then there is a statement that is propositionally equivalent to $P$ and is in conjuctive normal form i.e. it is the conjunction of disjunction of the $Q_ i$'s and their negation

Perhaps I am misunderstanding the question, but without knowing how $P$ is made from the $Q_i$ how I am able to convert $P$ in to CNF ?

Question 2 : Let $P$ be the statement "Howard fell" and $Q$ "Howard broke his leg.”"

With P and Q as given, under what conditions is the statement “P or Q” true when “or” is exclusive? Inclusive?

Surely "or" is always inclusive?

Update:

I apologize for this update. However A classmate of mine mentioned passingly that it was possible to proof Question 1 using Disjunctive normal form and De Morgan's laws

I am still unsure how to proof this effectively. Introduction and exhaustion have been suggested

Answer 1

For question 1, answer the question by induction on the length of $P$. For example, if $n=2$, you know that $P$ can be $Q_1\vee Q_2$ or $Q_1\wedge Q_2$ or $Q_1\implies Q_2$ or $Q_1\iff Q_2$ or... (and so on).

Each of the combinations can be written in CNF.

Then, for general $n$, you know that $P$ can be split into two shorter combinations, joined by a logical connective.

Answer 2

(1) Sure, write out the truth table for $\lnot P$, that gives you the DNF, then negate that and you have the CNF. Example:

$$P = Q_1 \text{ xor } (Q_2 \land Q_3)$$

$$\begin{array} {|c c c|c|} \hline Q_1 & Q_2 & Q_3 & \lnot P \\ \hline F & F & F & F \\ \hline F & F & T & F \\ \hline F & T & F & F \\ \hline F & T & T & T \\ \hline T & F & F & T \\ \hline T & F & T & T \\ \hline T & T & F & T \\ \hline T & T & T & F \\ \hline \end{array}$$

The $\lnot P = \text{true}$ lines give the DNF:

$$ \lnot P = (\lnot Q_1 \land Q_2 \land Q_3) \lor (Q_1 \land \lnot Q_2 \land \lnot Q_3) \lor (Q_1 \land \lnot Q_2 \land Q_3) \lor (Q_1 \land Q_2 \land \lnot Q_3) $$

Negate and you have your CNF:

$$ P = (Q_1 \lor \lnot Q_2 \lor \lnot Q_3) \land (\lnot Q_1 \lor Q_2 \lor Q_3) \land (\lnot Q_1 \lor Q_2 \lor \lnot Q_3) \land (\lnot Q_1 \lor \lnot Q_2 \lor Q_3) $$

(2) Inclusive:
Howard fell or Howard broke his leg, possibly both:
Is it possible that Howard fell and Howard broke his leg? Yes
Is it possible that Howard didn't fall and Howard broke his leg? Yes
Is it possible that Howard fell and Howard didn't break his leg? Yes
Is it possible that Howard didn't fall and Howard didn't break his leg? No

Exclusive:
Either Howard fell or Howard broke his leg:
Is it possible that Howard fell and Howard broke his leg? No
Is it possible that Howard didn't fall and Howard broke his leg? Yes
Is it possible that Howard fell and Howard didn't break his leg? Yes
Is it possible that Howard didn't fall and Howard didn't break his leg? No

Answer 3

"P or Q", with "or" inclusive (the "standard" $\lor$ connective of propositional logic), is true when at least one of P and Q is true.

We say "inclusive" because the truth of "P or Q" includes the case when both are true.

With the exclusive interpretation of "or", "P or Q" will be true when exactly one of P and Q is true, but not both.

Thus, in your example, assuming that "P and Q as given" means that both facts are true, the compound statement "P or Q" is true only with the inclusive "or".