Discrete Mathematics

Question

Determine whether ( 𝑝∨𝑞)∧(𝑝→𝑟)∧( 𝑞→𝑠)→𝑟∨𝑠 is a Tautology or a contradiction

Answer 1

I think with this kind of question, it can often help to figure out what the statement is actually saying, rather than just immediately plugging it into a truth table. So let's break down the steps involved.

(p ∨ q) ∧ (p → r) ∧ (q → s) → r ∨ s

The first statement, (p ∨ q), will evaluate true if p or q is true, and false otherwise.

Next, we'll look at (p → r), which we read as p implies r; this will read true if p and r are either both true or both false, and will be false otherwise.

The statement (q → s) reads similarly, just for q and s.

When we put this together, we get a statement that reads something like: if p or q is true, and p implies r is true, and q implies s is true, then r or s will be true. Thinking about this logically, we can see that this is in fact a tautology. If we reduce the problem to the form "A→B", where A=(p ∨ q) ∧ (p → r) ∧ (q → s), and B=r ∨ s, we can now look at it just in terms of whether this function can ever evaluate as false.

We know that the function 'implies' will always evaluate to true unless you have the situation where A is true and B is false. Now, let's consider what it means in our case if A is true: Then we know that either p or q is true, and that p implies r, and that q implies s. If p is true, then p implies r means that r is true, and r or s is true; if q is true, then q implies s is true, and therefore r or s is true. In both these cases, we get the result that the entire statement must evaluate as true as well. So since the statement is true if A is true, and it is true if A is false by the properties of the 'implies' function, the whole statement can only ever evaluate as true, and it is a tautology.

Of course, it is always good to go back and double check this kind of thing with a truth table, but I find that it can be helpful to just verbalize the problem and can make it feel much more intuitive and less mysterious. I know I'm coming a bit late to the problem, but I wanted to put this out in case anybody else is struggling with a similar problem and wanted a more intuitive-based answer.

Answer 2

p q r s p or q p->r q->s premise r or s Final

T T T T T T T T T T

T T T F T T F F T T

T T F T T F T F T T

T T F F T F F F F T

T F T T T T T T T T

T F T F T T T T T T

T F F T T F T F T T

T F F F T F T F F T

F T T T T T T T T T

F T T F T T F F T T

F T F T T T T T T T

F T F F T T F F F T

F F T T F T T F T T

F F T F F T T F T T

F F F T F T T F T T

F F F F F T T F F T

----------------------------------

(p or q) and (~q or r) and (~q or s) -> (r or s)

p and ~q or q and ~q or q and ~q or q and r and (~q or s) -> (r or s)

p and ~q or F or F or q and r and (~q or s) -> (r or s)

p and ~q or q and r and (~q or s) -> (r or s)

p or q and ~q or q and p or r and ~q or r and (~q or s) -> (r or s)

p or q and F and p or r and ~q or r and (~q or s) -> (r or s)

F -> (r or s)

which is true