Show that $A \to B, B \to C , \neg ( A\land C), A\lor C\implies C$

Using indirect method , Show that $$A \to B, B \to C , \neg ( A\land C), A\lor C\implies C$$

How can we show this,with the the help of truth table or some other method?

• If I try to prove it using truth table,still I can't get the answer Aug 10, 2013 at 12:42
• ^ stands for AND,. for OR,'->' stands for Conditional Aug 10, 2013 at 12:43
• Use \wedge for ^ and \vee for v (OR) and try to edit again Aug 10, 2013 at 12:45
• @Taylos: why so urgent? Aug 10, 2013 at 12:45

Try case analysis: Either $A$ or $\neg A$. Assume $A$. Then $B$ from $A$ and $A\to B$ using modus ponens. Then $C$ from $B$ and $B\to C$ using modus ponens. Now assume $\neg A$. Then $C$ from $\neg A$ and $A\lor C$ using disjunctive syllogism.

To reformulate this using inderect methods:

Assume $\neg C$. Then $\neg B$ from $B\to C$ by modus tollens. Then $\neg A$ from $A\to B$ using modus tollens. Also, from $\neg C$ and $A\lor C$ we get $A$ using disjunctive syllogism. Hence we get both $A$ and $\neg A$, hence $C$ by reductio ad absurdum.

• Thanks Sir..but I still did not understand Aug 10, 2013 at 12:52

Since you are dealing with argument (commas separate premises, while $\implies$ is meant as an inference marker ("Therefore,")), the way to show it is tautologically valid is to show that there is no valuation of its atoms that makes all the premises true and conclusion false.

So if you are using truth table, you should write all of the combinations of truth values of atoms (like when you are examining whether a given proposition is a tautology), and then calculate truth values of all the premises and a conclusion. If there is no line in the table that has value "true" for all the premises, and value "false" for the conclusion, your argument is valid.

One of the indirect ways to check this is by using the tree method: Start by writing down all the premises and a negation of the conclusion in a column. Then continue the column by writing at the bottom of it formula that needs to be true if one of the formulae already in the column are to be true. So, for example, if you have $A\land B$ in the column, both $A$ and $B$ need to be true, so continue the column by writing down $A$ and then $B$ below it. In cases where there are 2 possibilities, your column will branch into two. So, when you have a formula of the type $A\lor B$, this one is true when $A$ is true OR when $B$ is true, so you draw two branching lines below your column and write down below one line $A$, and below the other $B$. In the case where you have $A \to B$, this is equivalent with $\neg A \lor B$ so again you get 2 branches with $\neg A$ on one, and $B$ on the other.
Now, the moment you get two contradicting formulae on one of the paths trough the tree (following the branch from the bottom to the root at the top, you get one of the paths), you close of that path. If all the paths get closed that means that there is no valuation that makes all the premisses true and a conclusion false ie. the argument is valid.

I will try to describe how to do it with your argument: You start the tree by writing $A \to B$, $B \to C$ , $neg\ (A \land C)$, $A \lor C$, $\neg C$ one below the other. This gives you the initial trunk with premises and negation of conclusion. After that you add the first branching, and there you dissolve $A \lor C$, by adding $A$ to one branch and $C$ to the second. This second branch immediately closes of because when you look at the path that goes from the tip of the branch up to the root, there are both $C$ and $\neg C$ on that path. So, now you add to the left branch (the only one that remains open) another two branches where now you dissolve $neg\ (A \land C)$ so that you write $\neg A$ under one branch and $\neg C$ under the second one. Again, the branch with $\neg A$ on it closes off because it has $A$ on the same path.

Now, below the branch with $\neg C$ on its tip, you add another two branches where you dissolve $B \to C$, by adding $\neg B$ to the left branch and $C$ to the branch on the right. The latter branch closes off because it is part of the path that now has both $C$ and $\neg C$.

Finally, below the branch that has $\neg B$ on its tip, you add two branches where you dissolve $A \to B$ by adding $\neg A$ to the left branch, and $B$ to the right and both branches get closed then because the former is a part of the path that has both $A$ and $\neg A$ on it, and the latter of the one that has both $B$ and $\neg B$ on it. The fact that your tree doesn't have a path that remains open, or in other words that there are no valuations of the atoms that would yield true premisses and false conclusions, means that your argument is tautologically valid.

• Please break up your answer into paragraphs; this giant wall of text is completely unreadable. Also, please see here for a guide to writing math with MathJax, and see here for a guide to formatting posts with Markdown. Aug 10, 2013 at 14:24

Note that

$$(A \to B, B \to C , \neg (A \land C), A \lor C) \equiv ((A \to B) \land (B \to C) \land \neg (A \land C) \land (A \lor C)).$$

So, we want to prove that

$$X \to C$$

is always true for $X := ((A \to B) \land (B \to C) \land \neg (A \land C) \land (A \lor C))$. So, denoting truth as $1$ and lie as $0$, we get:

$$\begin{array}{ccc|cccccc|c} A & B & C & A \to B & B \to C & A \land C & \neg(A \land C) & A \lor C & X & X \to C \\ \hline 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 0 & 1 \end{array}$$

So, $X \to C$ is always true.

Be careful: you need to ignore $A \land C$ column when computing $X$, because that one is just a helper for the $\neg(A \land C)$ column, and not one of the subexpressions that are connected by "and" in $X$.

I'm not sure what you mean by "indirect" method, as we don't have such notion formally defined in logic. You have not mentioned any formalism, axiomatization or proof system. So, we can have a verbal reasoning as follows.

One of the well known ways to show that $q$ follows from $p$ ($p \Rightarrow q$) is to show that $p \land \lnot q$ is a contradiction.

Thus, we can simply consider $A \to B, B \to C, \neg(A \land C), A \lor C, \lnot C$ and show that it is a contradiction. Since we have both $A \lor C$ and we have $\lnot C$ are true, then we must have $A$ is true. On the other hand, since we have $A \to B$ and $A$ are both true, then $B$ must be true. Similarly, since we have both $B \to C$ and $B$ are true, we have $C$ is true. This is a contradiction, as we have both $C$ and $\lnot C$ are true.

Moreover, we have $A$ and $C$ are both true and at the same time we have $\lnot(A \land C)$ is true which is again a contradiction.

Assuming your commas are really $\land$-operators, it is easy to prove using cases (exhaustion). You are given two cases: $A\lor C$.

Case 1: Suppose $A$. Prove $C$ using detachment (modus ponens). Thus $A\implies C$

Case 2: Suppose $C$. It follows that $C\implies C$

In either case, we have $C$.

Note: We make no use of $\neg(A\land C)$

The last two assumptions directly relate $\;A\;$ and $\;C\;$, and simplifying them together gives \begin{align} & \lnot (A \land C) \land (A \lor C) \\ \iff & \;\;\;\;\;\text{"use DeMorgan on left hand side"} \\ & (\lnot A \lor \lnot C) \land (A \lor C) \\ \iff & \;\;\;\;\;\text{"rewrite both sides as implications,} \\ & \;\;\;\;\;\phantom{"}\text{using $\;P \to Q \iff \lnot P \lor Q\;$"} \\ & (A \to \lnot C) \land (\lnot C \to A) \\ \iff & \;\;\;\;\;\text{"definition of $\;\leftrightarrow\;$"} \\ (0) \;\; \phantom{\iff} & A \leftrightarrow \lnot C \\ \end{align} Now the first two assumptions obviously imply $\;A \to C\;$, and we can use $(0)$ to simplify that: \begin{align} & A \to C \\ \iff & \;\;\;\;\;\text{"substitute using $(0)$"} \\ & \lnot C \to C \\ \iff & \;\;\;\;\;\text{"rewrite using $\;P \to Q \iff \lnot P \lor Q\;$; simplify"} \\ & C \\ \end{align} This completes the proof.

I don't understand your question. You want to prove that $$A \to B, B \to C , \neg ( A\land C), A\lor C\implies C$$ It sounds like you want to prove that the statement is always true no matter what $A$, $B$, and $C$ are.

You mentioned in the comments that the "$,$" separating stuff left of $\implies$ is not to be understood as "and". Do they mean "or"?

To prove the above, you can take the approach outlined by @Hagen in his answer.

You need to consider the different possible "truth values" for $A$, $B$, and $C$.

So for example, you know that anything iplies true, so for all the options where $C$ is true, the statement is clearly true no matter what $A$ and $B$ are.

So no assume that $C$ is false. Then you have four cases to check:

1. $A$ true, $B$ true
2. $A$ true, $B$ false
3. $A$ false, $B$ true
4. $A$ false, $B$ false

Now if $C$ is false, then for the above statement to be true you would need $$A \to B, B \to C , \neg ( A\land C), A\lor C$$ to be false. And this is where one would need to know that the commas mean. If the commas mean "and" then in case 1. you have $B\to C$ is false, so the whole thing is false. In case 2. you have $A\to B$ false. In case 3. and 4. you have $A\lor C$ false.

@Taylos, judging by your comment on @Karl Damgaard Asmussen's answer (which is also misleading), it seems to me that your original problem is due to your not being sure what is required from you in the exercise.

There is a difference between testing by truth table whether a proposition is a tautology, and using truth table to test an argument. An argument cannot be a tautology, but it can be tautologically valid.

An argument consists of several propositions, one of which is a conclusion. The other propositions are premises.

Premises are separated from each other by commas, and between premises and a conclusion, an inference marker is added.

In your case it is $\implies$ that serves as an inference marker.

One thing that seems to cause confusion here is not making a distinction between inference marker and a sign for material conditional (or material implication) ' $\to$' which is a propositional connective and as such it is not used when argument is being represented, but when more complex proposition is being built from less complex ones.

So, to give an example: $(A \land B) \to C$ - is a proposition with material implication as the main connective. You can do a truth table test to see if it is tautology.

On the other hand, $A, B \implies C$ is a representation of an argument, not a single proposition. You can test it for tautological validity.

An argument is tautologically valid if and only if there is no valuation of atoms occuring in ts premises and conclusion that simultaneously makes ALL the premises true and a conclusion false.

So when you write down the table, what you should check is if there is a line on which ALL of he premises are true (in your case there are 4 of them) and conclusion is false. If there is no such line (and indeed in your example there is no such line), the argument is tautologically valid.

So to make it clear, it is irrelevant whether conclusion is made true by all valuations of the atoms. What is important is that all valuations that make all the premises true (if there are such valuations), also make the conclusion true.

Having said that, there is a metalogical result that shows that an argument of the type: $A,B,C \implies D$ is tautologically valid if and only if the proposition $((A \land B) \land C) \to D$ is a tautology.

Having that in mind, it can be shown that the argument in question is tautologically valid by showing that corresponding proposition is a tautology. Proposition corresponding to the argument in your example is $((((A \to B) \land (B\to C)) \land ( \neg(A\land C)))\land (A \lor C)) \to C$ and it is indeed a tautology.

(Assuming this is classical logic.)

The statement you posted is afaict not a tautology, so you cannot "show" that it is true. You can derive A and B assuming C.

Write up a truth table with columns for A, B, C (you will need 8 rows), then add a column for each of the four statements in the LHS, and add a column for the conjunction of all those four.

If it is a tautology, said conjunction should imply C, regardless of A and B.

• I did the same thing ,wrote truth table with col. A,B,C but still could not get C as my answer.Can u plz help me ? Aug 10, 2013 at 14:50
• If this is not a tautology, what do you make of the other answers that claim it is? Aug 10, 2013 at 18:17
• I believe that Karl wanted to say that it's not $X \leftrightarrow C$ ($X$ being the long expression; see my answer), but $X \rightarrow C$. So, you're not getting the same columns for $X$ and $C$, but instead only whenever $C$ has $0$, $X$ has $0$ as well. When $C$ is $1$, $X$ can still be anything. Aug 10, 2013 at 19:06
• @Thomas either OP edited the $\iff$ to $\implies$ or I misread it. Aug 13, 2013 at 11:19