Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
\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}
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?
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}$$
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.
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.
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.
tagged it as such in the proof commentary).
$\endgroup$
Jan 15, 2016 at 15:50
Another short proof in the notation used by the book Language, Proof and Logic. In language:
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:
Strictly speaking, you can stop here with the formal proof. But if you start attributing truth values, you can continue saying:
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.
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.
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.
