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?

• "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. – Henning Makholm Oct 19 '18 at 16:45

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).

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

• 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 ... – UnknownW Oct 18 '18 at 21:02
• @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. – Mauro ALLEGRANZA Oct 19 '18 at 6:18

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.