2
$\begingroup$

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?

$\endgroup$
1

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – Wyvern666
    Apr 30, 2013 at 18:11
  • $\begingroup$ 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... $\endgroup$
    – amWhy
    Apr 30, 2013 at 18:13
  • $\begingroup$ 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? $\endgroup$
    – Wyvern666
    May 1, 2013 at 0:31
  • 1
    $\begingroup$ 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. $\endgroup$
    – amWhy
    May 1, 2013 at 0:40
2
$\begingroup$

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


enter image description here

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This will would be a very direct demostration?. I have never seen that ⊨ symbol, is the same that =>? it means implication? $\endgroup$
    – Wyvern666
    Apr 30, 2013 at 18:20
  • 1
    $\begingroup$ @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. $\endgroup$ Apr 30, 2013 at 18:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .