# Prove that Statements forms are tautologies

Given variable statement forms $A$ and $B$. How to prove that if $(A\land B)$ is a tautology then $A$ and $B$ are tautologies too?.

Mi approach would be a proof by contradiction, something like: If we suppose $(A \land B)$ is a tautology but $A$ and $B$ are not tautologies, then $(A \land B)$ can't be a tautology and this will contradict the hypothesis, so $A$ and $B$ are tautologies. Is this correct or near correct?

• What is your definition of "tautology"? Apr 30, 2013 at 17:57

Your reasoning works, but it would be best to do this with more symbolic justification as to why "then $(A \land B)$ can't be a tautology.

...suppose [for the sake of contradiction) that $(A \land B)$ is a tautology but $A$ and $B$ are not [both] tautologies,

So $A \not\equiv T$ or $B\not\equiv T$ (or both).

then $(A \land B)$ can't be a tautology

because...there would then be at least one truth value assignments such that $A$ is false, or $B$ is false, and hence there would be truth value assignments such that $A\land B$ is false. This means that $A \land B \not\equiv T$. That is, it is not true that $A \land B$ is a tautology.

and this will contradict the hypothesis, so $A$ and $B$ [must both be] tautologies.

• Yes, i was on that path, considering truth value assignments. By the way i liked your answer before your edit, it was wrong or maybe unnecessary? Apr 30, 2013 at 18:11
• Yes, it was a bit off. If $A$ is not a tautology, e.g., then that isn't the same as saying it's a contradiction: (always false)...it just means it's not always true... Apr 30, 2013 at 18:13
• Just for curiosity, aboout: "...there would then be at least one truth value assignments such that A is false, or B is false...", Can that be expressed in a more simbolIc/formal way? maybe using the notation for truth functions? May 1, 2013 at 0:31
• Yes: we could say that there exist exactly three of the exactly four possible truth-value assignments to A, B such that $A\land B$ is false: (A, B) = (T, F); (A, B) = (F, T); (A, B) = (F, F). In each case, we have that $A \land B$ is false, hence the truth value of $A \land B$ depends on or is contingent on, the value of A, or of B, since one of the two is not a tautology, at least one of A, B is NOT guaranteed to be true...since one or the other or both can be false, so can $A\land B$ be false, which would mean $A\land B$ is not a tautology, which contradicts our premise. May 1, 2013 at 0:40

Your approach seems correct but it uses we know that $A∧B=T$ if $A,B$ are tautologies.

I always like to see these using Venn-Diagrams. $A,B$ be two sets and $A∧B$ represent the intersection

• Universal set=Tautology.
• empty ($\phi$ ) set represent contradiction.

. If $A∧B=\text{universal set}$ . Then both $A,B$ must be universal set, or tautologies.

The semantics of $\land$ is that

$$\Phi \models \phi \land \psi \mbox{ if and only if } \Phi \models \phi \mbox{ and } \Phi\models\psi \mbox{.} \tag 1$$

A sentence $\phi$ is a tautology if and only if

$$\models\phi \mbox{.} \tag 2$$

Suppose that $A \land B$ is a tautology. Then, by $(2)$, $\models A \land B$. Then, by $(1)$, $\models A$ and $\models B$. Then, by $(2)$, $A$ and $B$ are tautologies.

• This will would be a very direct demostration?. I have never seen that ⊨ symbol, is the same that =>? it means implication? Apr 30, 2013 at 18:20
• @Wyvern666 Wikipedia has an article on the double turnstile as it is called. In short, for a model $\cal M$, $\cal M \models \phi$ means that $\phi$ is true in $\cal M$. For a set of formulae $\Phi$, $\Phi \models \phi$ means that every model $\cal M$ that makes all of $\Phi$ true also makes $\phi$ true. When $\Phi$ is the empty set, we may write $\models\phi$, which means that $\phi$ is true in every model. In a propositional calculus, sentences that are true in every model (i.e., truth assignment) are tautologies. Apr 30, 2013 at 18:27