34
$\begingroup$

I am new to discrete mathematics, and I am trying to simplify this statement. I'm using a chart of logical equivalences, but I can't seem to find anything that really helps reduce this.

Which of these would help me to solve this problem? I realize I can covert $p \to q$ into $\lnot p \lor q$, but I'm stuck after that step. Any push in the right direction would be awesome.

$\endgroup$
  • 9
    $\begingroup$ This is en.wikipedia.org/wiki/Modus_ponens ¶ I'm not sure I see anything in your tables that would permit you to conclude $q$. $\endgroup$ – Brian Tung Jan 13 '16 at 21:34
  • $\begingroup$ After your conversion, use a distributive law. $\endgroup$ – John Jan 14 '16 at 0:45
  • 1
    $\begingroup$ @BrianTung You certainly can't conclude $p$ or $q$ from a tautology (which this is). $\endgroup$ – Daniel Wagner Jan 14 '16 at 1:01
  • 5
    $\begingroup$ Tons of good answers, but to phrase it in a more mundane way: "If it rains, cars gets what. It rained." Then to say that the "cars got wet," is of course a tautology... If someone said "When it rains, cars get wet, and it rained today!" Nobody would then ask "did the cars get wet?" $\endgroup$ – Andres Mejia Jan 14 '16 at 5:22
  • 2
    $\begingroup$ You'll never be asked to solve the really hard cases, but the general problem of determining whether a proposition is a tautology is actually really hard. It's co-NP-complete, as its complement is (a slight variation on) boolean satisfiability; a proposition is a tautology if and only if there is no satisfying assignment of its negation. $\endgroup$ – user2357112 Jan 14 '16 at 7:27

12 Answers 12

29
$\begingroup$

One approach is just to start writing a truth table - after all, there are only four cases. And this can be reduced: If $q$ is true, the statement is true (this is two cases). If $p$ is false, the statement is true because

$$p \wedge (p \to q)$$

is false. The only case that's left is when $p$ is true and $q$ is false, and I'll leave it to you to verify that the proposition is true in this case too.

$\endgroup$
  • $\begingroup$ In the case of p is true and q is false, I was under the impression that means p→q is false, which would imply the overall statement is false? What is my mistake in that logic? $\endgroup$ – 123 Jan 13 '16 at 21:44
  • 2
    $\begingroup$ @TK-421 If $p$ is true and $q$ is false, then $p \wedge (p \to q)$ is also false. $\endgroup$ – user296602 Jan 13 '16 at 21:46
  • 2
    $\begingroup$ Ohhh I think I get it. So since p∧(p→q) is false is that case, the overall implication is vacuously true? $\endgroup$ – 123 Jan 13 '16 at 21:48
  • 5
    $\begingroup$ Yes. ${}{}{}{}$ $\endgroup$ – user296602 Jan 13 '16 at 22:51
48
$\begingroup$

Is it a tautology? Yes

Why? Just draw the truth table and see that the truth value of the main implication is always 'true'. Here, I say '0' is 'false' and '1' is true: \begin{array}{|c|c|c|c|c|} \hline p & q & p\to q & p\land(p\to q) & (p\land(p\to q))\to q \\ \hline 0 & 0& 1&0&1\\ \hline 0 & 1& 1&0&1\\ \hline 1 & 0& 0&0&1\\ \hline 1 & 1& 1& 1& 1\\ \hline \end{array}

Edit: you can also say \begin{align}p \land (p \to q) &\equiv p \land (\lnot p \lor q)\\ &\equiv (p \land \lnot p) \lor (p \land q )\\ &\equiv \text {false} \lor (p \land q)\\&\equiv p \land q, \end{align}

that implies $q $.

Edit 2: this inference method is called modus ponens, and it is the simplest one.

For instance, say $p = $ it rains, $g = $ I get wet.

So, if we know that the implication if it rains, then I get wet is true (that is, $p\to q $) and It rains ($p $), what can we infere? It is obvious that I get wet ($q $).

Note that, even though $p \land (p\to q) $ is not verified, as $p\land (p\to q) \to q$, the main implication is verified.

$\endgroup$
23
$\begingroup$

\begin{align} (p \land (p \implies q)) \implies q & \equiv \lnot (p \land (p \implies q)) \lor q \\ & \equiv \lnot (p \land (\lnot p \lor q)) \lor q \\ & \equiv (\lnot p \lor \lnot (\lnot p \lor q)) \lor q \\ & \equiv (\lnot (\lnot p \lor q) \lor \lnot p) \lor q \\ & \equiv \lnot (\lnot p \lor q) \lor (\lnot p \lor q) \\ & \equiv \lnot w \lor w \quad \text{where}\ \ w \equiv (\lnot p \lor q) \\ & \equiv T \end{align}

$\endgroup$
22
$\begingroup$

Start with the given statement,

$$ [p \land (p \rightarrow q)] \rightarrow q.$$

As you noticed, from the first logical equivalence in Table 7, you can replace the part in the round brackets to get the equivalent statement

$$ [p \land (\lnot p \lor q)] \rightarrow q.$$

By the distributive law, this is equivalent to:

$$ [(p \land \lnot p) \lor (p \land q)] \rightarrow q.$$

Negation Law:

$$ [\mathbf F \lor (p \land q)] \rightarrow q.$$

Can you continue from there?

$\endgroup$
20
$\begingroup$

It seems that your tables miss an important rule, so important it has a name, which is "modus ponens". It can be stated as $p \land (p \rightarrow q) \equiv p \land q$. It can be derived from first rule of Table 7, and various laws from Table 6:

$$\begin{align} p \land (p \rightarrow q) &\equiv p \land (\neg p \lor q) \\ &\equiv (p \land \neg p) \lor (p \land q) & \textrm{(distribution)}\\ &\equiv p \land q & \textrm{(negation and identity)} \end{align}$$

So your initial statement becomes $$ (p \land q) \rightarrow q$$ which is clearly a tautology, but it can be formally proved using de Morgan's law:

$$\begin{align} (p \land q) \rightarrow q &\equiv \neg (p \land q) \lor q \\ &\equiv \neg p \lor \neg q \lor q & \textrm{(de Morgan and associativity)}\\ &\equiv \neg p \lor T & \textrm{(negation)}\\ &\equiv T & \textrm{(domination)} \end{align}$$

$\endgroup$
  • 3
    $\begingroup$ +1 for actually giving a clear and readable derivation using the rules in the OP's table. $\endgroup$ – Ilmari Karonen Jan 14 '16 at 12:15
15
$\begingroup$

Alternatively you can argue by contradiction.

Suppose it was not a tautology, so there is a situation where the statement evaluates as false. This must mean that $q$ is false and $[p \land (p \to q)]$ is true (if we want $A \to B$ to be false, we need $A$ true and $B$ false).

Hence both $p$ and $p \to q$ are true. But this gives $q$ true, which is a contradiction.

This technique is particularly slick for three-'variable' statements as it saves you doing a giant 8-row truth table.

$\endgroup$
  • $\begingroup$ To emphasize: when $\lor$ (and $\to$ can be rewritten as such) is involved en.wikipedia.org/wiki/Reductio_ad_absurdum is great because there is only one case where it can be false. $\endgroup$ – chx Jan 15 '16 at 15:32
9
$\begingroup$

Sometimes you can think of it in a constructive way. Suppose that distinct variables stand for distinct object types and stands for transforms. You have a (copyable) object of type p and a transform from p to q. Does it imply you can get an object of type q? Obviously, yes. You just need to use the transform on that object. This way of thinking is described by the BHK interpretation of logic. A formal proof that this is a tautology would be written as

proof : (p, p -> q) -> q
proof (x, f) = f x

and has the handy property of being automatically checkable on a PC by proof systems such as Agda or Idris. It's worth mentioning that this approach wouldn't work as well if you need a double negation law somewhere in your proofs.

$\endgroup$
7
$\begingroup$

I thought I would, for completeness, provide an unnecessarily thorough, but perhaps helpful, proof with an algebraic flavor that uses the different laws provided in the table(s): \begin{align} [p\land(p\to q)]\to q&\equiv \neg[p\land(\neg p\lor q)]\lor q\tag{table 7, rule 1}\\[0.5em] &\equiv [\neg p\lor(p\land\neg q)]\lor q\tag{De Morgan}\\[0.5em] &\equiv [(\neg p\lor p)\land(\neg p\lor\neg q)]\lor q\tag{Distributivity}\\[0.5em] &\equiv [\mathbf{T}\land(\neg p\lor\neg q)]\lor q\tag{Negation}\\[0.5em] &\equiv (\neg p\lor\neg q)\lor q\tag{Identity}\\[0.5em] &\equiv \neg p\lor(\neg q\lor q)\tag{Associativity}\\[0.5em] &\equiv \neg p\lor\mathbf{T}\tag{Negation}\\[0.5em] &\equiv \mathbf{T}\tag{Domination} \end{align} Of course, the above proof has everything spelled out and leaves nothing to the imagination. A more useful technique for determining whether or not you have a tautology on your hands is to argue directly by showing that if the hypothesis is true then so is the conclusion (it is a neat little "trick" that simplifies things a bit). For example, in your case, you would argue as follows to employ this trick:

Assume the hypothesis is true. Then $p$ must be true. Since $p\to q$ must also be true, we necessarily have that $q$ is true as well. Thus, the conclusion (i.e. $q$) is true, as desired.

The above is simply a "snappy" explanation of why you have a tautology but proofs with a more algebraic flavor, I find, are more satisfactory. But sometimes they can get a little out of hand.

$\endgroup$
  • $\begingroup$ I'd say your proof actually does not have everything spelled out, because you didn't proof p v ~p. $\endgroup$ – Alex Jan 15 '16 at 14:10
  • 2
    $\begingroup$ @ultrabowser That is simply the law of excluded middle. Also, the equivalence $p\lor\neg p\equiv\mathbf{T}$ is given in OP's table as a negation law (which is why I tagged it as such in the proof commentary). $\endgroup$ – Daniel W. Farlow Jan 15 '16 at 15:50
4
$\begingroup$

Another short proof in the notation used by the book Language, Proof and Logic. In language:

  1. Suppose that P and if P then Q.
  2. I just said P.
  3. I just said if P then Q.
  4. So Q.
  5. Our assumption (1) appearently leads to Q. enter image description here
$\endgroup$
1
$\begingroup$

While there are many good algebraic answers (I find these to be the best responses, given the OP's formulation of the question), here is another way of proving it using the rules you provided. Often you will find that you will need only a surprisingly small subset of such rules to prove or disprove statements. You can do a web search for "logical system".

Here is one possible proof, where all these items denote terms in an equivalence:

  1. $[ p \land (p \to q)] \to q$
  2. $ \neg [p \land (p \to q)] \lor q$ (1st rule from table 7 for the outer implication)
  3. $ \neg p \lor \neg (p \to q) \lor q $ (de Morgan)
  4. $\neg p \lor \neg (\neg p \lor q) \lor q $ (1st rule from table 7 for the inner implication)
  5. $ \neg p \lor (p \land \neg q) \lor q$ (de Morgan)
  6. $ [(\neg p \lor p) \land (\neg p \lor \neg q)] \lor q $ (distribution over the first two terms)
  7. $ q \lor [(\neg p \lor p) \land (\neg p \lor \neg q)] $ (commutation, from table 6)
  8. $ [( \neg p \lor p) \lor q ] \land [q \lor (\neg p \lor \neg q)] $ (distribution)
  9. $ [( \neg p \lor p) \lor q ] \land [q \lor (\neg q \lor \neg p)] $ (commutation)
  10. $ [( \neg p \lor p) \lor q ] \land [(q \lor \neg q) \lor \neg p] $ (association)

Strictly speaking, you can stop here with the formal proof. But if you start attributing truth values, you can continue saying:

  1. $ (\mathbf{T} \lor q) \land (\neg p \lor \mathbf{T}) $ (negation laws)
  2. $ \mathbf{T} \land \mathbf{T} $ (domination twice)
  3. $\mathbf{T}$ (by definition of '$\land$')

Although there are many shorter proofs (see, for example, other people's solutions), this was to show you that you can most often reach, tediously and mechanically, a string of conjunctions of disjunctions or disjunctions of conjunctions which will reduce to truth.

$\endgroup$
  • $\begingroup$ It seems that what you are advocating is to convert to a normal form (CNF or DNF)? Or just listing that as one possibility? $\endgroup$ – Daniel W. Farlow Jan 17 '16 at 13:47
  • $\begingroup$ As I was saying, converting to CNF/DNF, as you correctly name what I did, is just one possibility. There is nothing to advocate for here, but it is useful to remember this general approach. :) $\endgroup$ – Nolatar Jan 18 '16 at 10:19
0
$\begingroup$

Here's another way to look at propositional logic questions, which can be especially useful if you are interested in computer science at it allows you to gain some exposure to examples of binary functions.

We can represent $p$ and $q$ by bits (taking on the value of either 0 or 1), where the case $p=1$ corresponds to the statement that $p$ is true, and the case $p=0$ similarly means that $p$ is false.

If we consider two bits $p$ and $q$, then we can analyze the truth value of propositions like $p \wedge q$ or $p \rightarrow q$ by creating binary functions (i.e. we evaluate the value of the function modulo 2) that take $p$ and $q$ as input. Then, given truth values of $p$ and $q$, we can evaluate our function to tells us whether the desired proposition is true or false.

For example, consider the proposition $\neg p$. This can be associated with the function $1 + p$ where we take our sum modulo 2, as if $p=0$, then $1+p = 1$, and if $p=1$, $1+p = 0$ when taken modulo 2 (which we will do without saying in the rest of the examples).

To denote the association between a proposition and a binary function, we will use the symbol $\sim$. Therefore one would say that $\boxed{\neg p \sim 1 + p}$.

In order for a proposition to be a tautology, we need that the corresponding function always evaluates to 1, regardless of the input values. Now we will explain the building-block functions that we will need to use in order to discuss the function associated with the proposition $[p \wedge (p \rightarrow q)] \rightarrow q$.

First let's think about $p \wedge q$. If we consider the function $pq$, then we see that $pq = 1$ if and only if $p=q=1$. Analogously, the proposition $p \wedge q$ is true if and only if $p$ is true and $q$ is true, so we see that the value of the binary function $pq$ corresponds to the truth value of the proposition $p \wedge q$. Thus we have $\boxed{p \wedge q \sim pq}.$

Similarly, for $p \vee q$, we can find the associated function $p + q + pq$. To confirm this, we see that $p + q + pq = 0$ only when $p = q =0$, whereas otherwise $p+q+pq$ will return the value 1 when taken modulo 2. We then write that $\boxed{p \vee q \sim p + q + pq}$.

Now, for the proposition $p \rightarrow q$, we can use its equivalent characterization as $\neg p \vee q$ in order to find the associated function $$(1+p) + q + (1+p)q = 1 + p + 2q + pq = 1 + p + pq \Longrightarrow \boxed{p \rightarrow q \sim 1 + p + pq} $$ where we used the fact that $2x = 0$ for a binary variable $x$ because $2x = 0$ modulo 2 for both $x=0$ and $x=1$.

Now we can put things together. We see that the product $$p (1 + p + pq) = p + p^2 + p^2 q = p + p + pq = 2p + pq = pq$$ where we used the fact that $x^2 = x$ for binary variable $x$, and therefore we see that $$p \wedge (p \rightarrow q) \sim pq $$

Now, to find the associated function for $[p \wedge (p \rightarrow q)] \rightarrow q$, we consider the expression $$1 + (pq) + (pq)(q) = 1 + pq + pq^2 = 1 + 2 pq = 1 $$ so we have that $$\boxed{[p \wedge (p \rightarrow q)] \rightarrow q \sim 1} $$ and we have verified that our proposition is a tautology.

$\endgroup$
0
$\begingroup$

My English is not good enough but I have knowledge about logic and proof. So if I use English wrongly I'm sorry about it. Please,tell me and teach me.Let's start. Assign that : T is TRUE F is FALSE I would use contradiction to proof that [p∧(p→q)]→q is tautology or not.

suppose that [p∧(p→q)]→q ≡ F

[ a→b truth table ]

from a→b truth table : T→T ≡ T , T→F ≡ F , F→T ≡ T , F→F ≡ T we know a→b ≡ F in only 1 case that a ≡ T , b ≡ F . From assumption : [p∧(p→q)]→q ≡ F therefore [p∧(p→q)] ≡ T , q ≡ F consider [p∧(p→q)] ≡ T

[a∧b truth table]

From a∧b truth table : we know that T∧T ≡ T , T∧F ≡ F , F∧T ≡ F , F∧F ≡ F we know a∧b ≡ T in only 1 case that a ≡ T , b ≡ T

From : [p∧(p→q)] ≡ T

therefore p ≡ T and (p→q) ≡ T consider (p→q) ≡ T

from above we know that : q ≡ F

     (p→q) ≡ T
     (p→F) ≡ T

therefore p ≡ F but from the above we know that p ≡ T

contradict! therefore assumption is false. [p∧(p→q)]→q ≡ F is not true. Therefore [p∧(p→q)]→q is tautology.

$\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.