semantic entailment, finding a proof
I was given the assignment to find a proof for the following
$$A, A\rightarrow B, C\rightarrow\lnot B\models\lnot C$$
I understand that when all the hypothesizes of an argument are true, it semantically implies the conclusion. I know how to proof the validity of an argument but have no idea what I am required to do in order to answer the question. What is the solution for the assignment?
$\endgroup$4 Answers
$\begingroup$You could also argue as follows:
We're given $A$ and $A \rightarrow B$. Hence we know $B$.
$\neg C = C \rightarrow False$.
Adding $C$ to assumptions, we need to prove $False$.
$\neg B = B \rightarrow False$, yielding $C \rightarrow B \rightarrow False$.
Here we can make $False$ with $C$ and $B$ as $C \rightarrow B \rightarrow False$ = $(C \land B) \rightarrow False$. Using ex falso quodlibet, we can show just about anything - even $False$.
$\endgroup$ 3 $\begingroup$I understand that when all the hypothesizes of an argument are true, it semantically implies the conclusion. I know how to proof the validity of an argument but have no idea what I am required to do in order to answer the question.
Yes, Semantic Entailment means that the conclusion will always be valued as true whenever we value all of the premises as true.
So, you are required to show that every assignment of values for the literals in $\{A,B,C\}$ which holds all of the statements in $\{A, A\to B, C\to\lnot B\}$ as true also holds the statement in $\{\lnot C\}$ as true.
You begin by noting that the only assignments which values statement $A$ as true will obviously be those which hold literal $A$ as true. So...
$\endgroup$ $\begingroup$What you need to do is to start with an assignment which gives "true" to $A, A\rightarrow B$ and $C\rightarrow\lnot B$, and prove that $\lnot C$ also get assigned the truth value "true".
You can do this using a truth table and consider all the eight assignments to $A,B$ and $C$; then isolate those which give "true" to the three assumptions (hint: there is exactly one like that).
$\endgroup$ 5 $\begingroup$To prove the result would mean to use inference rules rather than a truth table to derive the conclusion. Here is one way to prove the result using a Fitch-style natural deduction:
The premises are on the first three lines. On line 4 I use conditional elimination (→E) and reference the conditional on line 2 and the antecedent on line 1. The rule allows me to derive line 4.
I have a rule called modus tollens (MT) in the proof checker and I would like to use that to derive $¬C$ from the third premise and line 4, $B$. However the proof checker requires that $B$ be in the form $¬¬B$. I don't mind these requirements. They force me to follow the permitted inference rules and the proof checker confirms my steps. Besides it is easy to derive $¬¬B$ by deriving a contradiction and using negation introduction (¬I) on line 7. This allows me to complete the proof on line 8.
There are other ways to write a proof perhaps using different inference rules and different proof checkers. If one follows the rules, assuming they are a complete and sound set of rules, one should be able to derive the goal because the truth table shows that the result is true.
If what you are looking for is to show semantic entailment, a truth table should work:
Conjoin the premises as implying the conclusion and place this in a truth table generator. This should result in a tautology which is signaled by the column under the implies symbol being true. That is, for all valuations of the atomic sentences, the conditional is true.
Kevin Klement's JavaScript/PHP Fitch-style natural deduction proof editor and checker
P. D. Magnus, Tim Button with additions by J. Robert Loftis remixed and revised by Aaron Thomas-Bolduc, Richard Zach, forallx Calgary Remix: An Introduction to Formal Logic, Fall 2019.
Michael Rieppel, Truth Table Generator
$\endgroup$ 2
