Is the statement
[(P → (Q ∧ ¬R)) ∧ (¬S → (P ∨ ¬V )) ∧ R ∧ V] → S
a tautology? If so, give a formal proof that it is without using a truth table. I have no idea how to solve this problem. Can anyone help me?
(P→(Q∧¬R))∧(¬S→(P∨¬V))∧R∧V
(¬P∨(Q∧¬R))∧((¬S∧¬P)→¬V)∧R∧V
((¬P∨Q)∧(¬P∨¬R))∧(¬(S∨P)→¬V)∧R∧V
((¬P∨Q)∧(¬P∨¬R))∧(V→(S∨P))∧R∧V
(¬P∨Q)∧(¬P∨¬R))∧(¬V∨(S∨P))∧R∧V
Thank you in advance.
On
(1) Suppose ( for refutation ) there is a possible case /truth assignment such that the formula is false.
(2) It means that ( in that supposed assignment) the antecedent is true and the consequent false.
So $S$ is false, and all the conjuncts of the antecedent are true.
(3) So , in particular , $R$ is true and $(P \rightarrow (Q\land\neg R))$ is also true.
Since $R$ is true, $(Q\land\neg R)$ is false. So , the only way for $(P \rightarrow (Q\land\neg R))$ to be true is that the antecedent $P$ is false. ( For a true conditional with a false consequent cannot have a true antecedent).
(4) The problem is that $S$ is false by hypothesis. So : $\neg S\rightarrow (P\lor\neg V))$ is a true conditional with a true antecedent. It must therefore have a true consequent.
So the consequent $(P\lor\neg V))$ has to be true. This disjunction already has a false disjunct ( since V is true in our assignment, by step $(2)$ ). So the first disjunct , namely $P$, has to be true.
(5) But, this disjunct that has to be true, is false ( by step (3)); hence a contradiction.
Conclusion : no consistent/ possible truth assignment in which the formula is false.
Note : more on this method in Mendelson, Outline Of Boolean Algebra and Switching Cirduits.
Note :
The principles I use here are
(1) A conditional is false iff its antecedent is true and its consequent false.
(2) A conjunction is true iff all its conjuncts are true.
(3) A disjunction is true iff at least one of its disjuncts is true.
(4) No proposition can be true and false at the same time.
On
Instead of a full truth-table, you can do what is called a 'short truth-table' method. The basic is to try and set one or more statement to true or false depending on what you're interested in, and see what is forded from there. So, in this case, we have a single statement, and since we're interested in whether it is a tautology or not, the truth-vale of interest is in it being False. That seems counter-intuitive, but note that if the statement can be False, then it is not a tautology, while if it cannot be false then it is. So, the possibility of it being False is the crucial possibility that will provide you with an answer.
So, let's set the statement to False, and see what happens:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R ∧& \land & V] & \rightarrow & S\\ &&&&&&&&&&&&&&&&&&&&&F& \end{array}
Well, there is only one way for a conditional to False, and that is for the antecedent to be True and the consequent False:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &&&&&&&&T&&&&&&&&&T&&T&&F&F \end{array}
This of course means that all individual conjuncts have to be True:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &&T&&&&&&T&&&T&&&&&&T&T&T&T&F&F \end{array}
Now let's copy some of the already forced values of atomic propositions $R$, $V$, and $S$:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &&T&&&&T&&T&&F&T&&&&T&&T&T&T&T&F&F \end{array}
Work out negations:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &&T&&&F&T&&T&T&F&T&&&F&T&&T&T&T&T&F&F \end{array}
Let's focus on $\neg S \rightarrow (P \lor \neg V)$. Since we're trying to make this True, and $\neg S$ is already forced to be True, that means $P \lor \neg V$ should be True as well:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &&T&&&F&T&&T&T&F&T&&T&F&T&&T&T&T&T&F&F \end{array}
which forces $P$ to be True:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &&T&&&F&T&&T&T&F&T&T&T&F&T&&T&T&T&T&F&F \end{array}
Copy value of $P$:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &T&T&&&F&T&&T&T&F&T&T&T&F&T&&T&T&T&T&F&F \end{array}
Since $\neg R$ is False, it follows that $Q \land \neg R$ is also False:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &T&T&&F&F&T&&T&T&F&T&T&T&F&T&&T&T&T&T&F&F \end{array}
But now we have a problem (a contradiction!): $P \rightarrow (Q \land \neg R$ is supposed to be True, but $P$ is True and $Q \land \neg R$ is False:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &\color{red}T&\color{red}T&&\color{red}F&F&T&&T&T&F&T&T&T&F&T&&T&T&T&T&F&F \end{array}
This means that, contrary to our assumption, the whole original statemnt can not be False ... meaning that it is a tautology.
Now, this seems like a lot of work, but here is the whole process formalized in a single row, where I use indices to indicate the order in which I place Truth-values:
\begin{array}{cccccccccccccccccccc} [(&P& \rightarrow & (Q & \land & \neg & R&)) & \land & (\neg & S & \rightarrow & (P & \lor & \neg & V &)) & \land & R & \land & V] & \rightarrow & S\\ &\color{red}T_{17}&\color{red}T_6&&\color{red}F_{18}&F_{12}&T_{11}&&T&T_{13}&F_{10}&T_5&T_{16}&T_{15}&F_{14}&T_9&&T_4&T_7&T_3&T_8&F_1&F_2 \end{array}
And that's it! So note that this single row would show up in a full truth-table .. together with a whole bunch of other rows. But in this method, you effectively 'home in' directly on the row(s) that would tell you the answer to the your original question. Once you get used to this method, it is actually pretty darn fast, and in fact often a very quick method of choice for experienced logicians. Also note that it is effectively the method as described in the Answer provided by Ray Littlerock ... except now you can see how you can nicely formalize this.
There is, unfortunately, a drawback to this method, and that is that sometimes 'moves' are not forced, and so you won't get your answer ... unless you start to consider some options. Well, one method of systematically keeping track of such choices is the 'tree method' or 'tableaux method' as given in the Answer provided by user400188.
So yes, lots of ways to avoid a full truth-table!
On
[(P → (Q ∧ ¬R)) ∧ (¬S → (P ∨ ¬V )) ∧ R ∧ V] → S
First I translate the "implies" operators to more basic ones:
¬[(¬P ∨ (Q ∧ ¬R)) ∧ (S ∨ (P ∨ ¬V)) ∧ R ∧ V] ∨ S
and then it's all algebra.
[¬(¬P ∨ (Q ∧ ¬R)) ∨ ¬(S ∨ (P ∨ ¬V)) ∨ ¬R ∨ ¬V] ∨ S
(P ∧ ¬(Q ∧ ¬R)) ∨ (¬S ∧ ¬(P ∨ ¬V)) ∨ ¬R ∨ ¬V ∨ S
(P ∧ (¬Q ∨ R)) ∨ (¬S ∧ ¬P ∧ V) ∨ ¬R ∨ ¬V ∨ S
(P ∧ ¬Q) ∨ (P ∧ R) ∨ (¬S ∧ ¬P ∧ V) ∨ ¬R ∨ ¬V ∨ S
(P ∧ ¬Q) ∨ P ∨ (¬S ∧ ¬P) ∨ ¬R ∨ ¬V ∨ S
(P ∧ ¬Q) ∨ P ∨ ¬S ∨ ¬R ∨ ¬V ∨ S
P ∨ ¬S ∨ ¬R ∨ ¬V ∨ S
P ∨ ¬R ∨ ¬V ∨ ¬S ∨ S
P ∨ ¬R ∨ ¬V ∨ 1
1
[(P → (Q ∧ ¬R)) ∧ (¬S → (P ∨ ¬V )) ∧ R ∧ V] → S (0)
The easiest way to show that (0) is a tautology without using a truth table or Karnough map, is with a proof tree.
To use this method, we will first assume that (0) is false, and derive a contradiction from that assumption. Since our assumption led to a contradiction, it must have been wrong, so (0) must not be false, that is, (0) is a tautology.
In the following proof tree, branches will be marked with an X when a contradiction is arrived at. The aim is to close every branch, so that there is no way for the premises to be true.
As your attempt at the question seems to follow a different proof method, I have answered this question a different way bellow. Here I re-write (0) a number of different ways until it simplifiers to ($\lnot S)\lor S$, as you seemed to be doing.