353 views

Let $F$ and $G$ be two propositional formula. Which of the following is/are TRUE?

1. If $F \rightarrow G$ is satisfiable and $F$ is satisfiable, then $G$ is satisfiable.
2. If two statements(propositions) are logically equivalent, then so are their negations.
3. If a statement $p$ is a contradiction, then, for any statement $q$, the statement $p \rightarrow q$ is a tautology.
4. If a statement $q$ is true, then, for any statement $p$, the statement $p \rightarrow q$ is true.

I am not able to understand why Option A is not true.

Given, F$\implies$G is satisfiable and F is satisfiable.

It means atleast one row in Truth Table of both F and F$\implies$G is True.

We know atleast one row must be True, it doesn't say what other rows should be.

Some rows in F can be False. Some rows in F$\implies$G can be False.

Now, suppose G is contradiction (all rows False). Then, it may happen one row of F is False. That makes corresponding row of F$\implies$G True.

Thus, both given conditions can be fulfilled even when G is not satisfiable.

Counter-Example for (A):

$F: p$ and $G: p \wedge (\lnot p)$

$F \rightarrow G \equiv p \rightarrow p \wedge (\lnot p) \equiv \lnot p \vee (p \wedge (\lnot p)) \equiv (\neg p \vee p) \wedge (\neg p \vee \neg p) \equiv T \wedge \neg p \equiv \neg p$

Or roughly, $F \rightarrow G$ is $\bar{p} + p\bar{p} = \bar{p}(1+p) = \bar{p}$

So, here, both $F$ and $F \rightarrow G$ are satisfiable but $G$ is not satisfiable.

Option (A)This option says That F→ G is satisfiable means it can be true or false, also F is Satisfiable meaning it can be true, now does this mean that if both above conditions are true then G is also satisfiable?

No, If we take g as contradiction Then f alone can decide the value of F→ G , when f is true the implication is false since true → False is False and when F is False , the implication is true, False → Anything is true.

So even if F→ G is satisfiable and F is satisfiable G need not be satisfiable, it can be unsatisfiable/Contradiction

This way we can say option is isn’t true

Option (B) This statement can be understood in multiple ways, one way is to think of logical equivalence and equal sign, When we take negative on both sides we still end up with an equality.

another way is to take its formula : A↔ B means both are same/equal/equivalent/both true or false. Since their truth values will be same so negation will be same too, 0↔ 0 taking its negation 1 ↔ 1

So option B is true

Option (C) This a simple fact about implication, if antecedent is false then whatever is consequent the implication is true since false → anything is true

So option c is true

Option (D) This is another observation of implication, The only case in which implication is false is when q of p→ q is false and p is true, here if q is always true then p→ q will always be true

This way option B,C,D are true
by