0
$\begingroup$

Definition: Let $p$ and $q$ be two compound statements. I read that, If $p\implies q$ is a tautology, then $q$ is said to be a logical consequence of $p$.

Furthermore, it notes that the statement $p\implies q$ is automatically true when $p$ is false, and saying that $p\implies q$ is a tautology actually means that $q$ is true, when $p$ is true.

I do not really understand the last sentence (the bold ones). Can $p\implies q$ not be a tautology, when $p$ is false, or when $p$ and $q$ are both false?

For example, let $p$ and $q$ be simple statements, and we know that the compound statement $[(p\implies q)\wedge p]\implies q$ is a tautology, which can be shown by making a truth table, see for example URL (generate "((p>q)&p)>q" without the "-signs).

Does the note say that we only need to check when $(p\implies q)\wedge p$ is true, which only happens when $p$ and $q$ are true (as shown in the truth table), and we forget the rest of the combinations?

$\endgroup$
  • $\begingroup$ "Saying that $p\implies q$ is a tautology actually means that $q$ is true, when $p$ is true" sounds almost tautological already. Better just ignore that sentence and go by the general definition: A propositional formula is a tautology when its truth value is "true" for all possible truth assignments to the atomic formulas in it. $\endgroup$ – Henning Makholm Oct 19 '18 at 16:45
1
$\begingroup$

Furthermore, it notes that the statement $\def\implies{\to}p\implies q$ is automatically true when $p$ is false, and saying that $p\implies q$ is a tautology actually means that $q$ is true, when $p$ is true.

I do not really understand the last sentence (the bold ones). Can $p\implies q$ not be a tautology, when $p$ is false, or when $p$ and $q$ are both false?

As stated, $p\to q$ is true when $p$ is false; that is a sure thing.   Thus we only need to examine what happens to $p\to q$, when $p$ is true.   Hence $p\to q$ will be a tautology if we cannot have $q$ be false while $p$ is true.

For example: $p\to (r\to p)$ is a tautology because $r\to p$ is alway true when $p$ is true.   Now $r\to p$ may be false when $p$ is false (ie when $r$ is true), but that doesn't matter because $p\to (r\to p)$ is true when $p$ is false whatever $r\to p$ might be.

On the other hand $p\to\lnot p$ is not a tautology because, clearly, $\lnot p$ may$^\star$ be false when $p$ is true. ($^\star$ in fact, it must be so).

$\endgroup$
0
$\begingroup$

$p \to q$ is TRUE either when $q$ is TRUE or when $p$ is FALSE.

Equivalently, $p \to q$ is FALSE exactly when $p$ is TRUE and $q$ is FALSE.

A formula is a tautology when it is always TRUE.

Thus, in order for $A \to B$ to be a tautology, we have to exclude the case : $A$ TRUE and $B$ FALSE.

In order to verify that a fromula is a tautology we have to build a truth table and check that the formula is TRUE in every row.

In order to verify that $B$ is a tautological consequence of $A$ we have to build a truth table for both formulas $A$ and $B$ and check that in every row where $A$ is TRUE also $B$ is TRUE.

$\endgroup$
  • $\begingroup$ Okay, so if we take an example, say $(p\implies q)\wedge p$, which is TRUE when both $p$ and $q$ are TRUE, otherwise it is FALSE. So, when $p$ and $q$ are both TRUE, so does $[(p\implies q)\wedge p] \implies q$, and therefore it is a tautology. Is my understanding correct on this example? Thank you for your time ... $\endgroup$ – UnknownW Oct 18 '18 at 21:02
  • $\begingroup$ @UnknownW - $(p \to q) \land p$ is NOT a taut, because when when $p$ is False the formula is FALSE. A tautology is always TRUE. $[(p \to q) \land p] \to q$ instead, is taut. $\endgroup$ – Mauro ALLEGRANZA Oct 19 '18 at 6:18
0
$\begingroup$

Does the note say that we only need to check when $(p\implies q)\wedge p$ is true, which only happens when $p$ and $q$ are true (as shown in the truth table), and we forget the rest of the combinations?

No. Using only 6 basic, self-evident principles of natural deduction (Intro $\land$, Elim $\land $, Intro $\to$, Elim $\to$, Intro $\neg$, Elim $\neg\neg$), we can actually prove each of the following (each corresponding to a line of the truth table):

Line 1: $A \land B \to (A \to B)$

Line 2: $A\land \neg B \to \neg(A \to B)$

Line 3: $\neg A \land B\to (A\to B)$

Line 4: $\neg A \land \neg B \to (A \to B)$

Thus we can derive the entire truth table for material implication.

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