Proving the Implication of p and (p -> q) to q without Truth Tables

[member 587159]

Hello everyone!

I want to proof that:

$p \land (p \to q) \Rightarrow q$

I know this is a quite trivial problem using truth tables, however, I want to do it without it. As I'm learning this myself, is this the correct approach?

$p \land (p \to q)$
$\iff p\land (\neg p \lor q)$
$\iff (p \land \neg p) \lor (p \land q)$ (distributive law)
Now, $p \land \neg p$ is a contradiction (see the questions below)
$\iff (p \land q)$

Now, it is clear, that $p \land q \Rightarrow q$

Also, I have some additional questions.

1) Suppose there is a contradiction (or tautology) r. Can we always say then, that:
$r \lor p \iff p$
2) Suppose there is a contradiction r. Can we always say then, that:
$r \land p$ is a contradiction?
3) Suppose there is a tautology r. Can we always say then, that:
$r \land p \iff p$

Thanks in advance.

 

[andrewkirk]

Hello. How one proves that depends on what system of logical axioms and rules of inference one is using.

If one is not using truth tables, one uses axioms and rules of inference. Two well known systems are (a) the Hilbert System and (b) Natural Deduction. Each has a set of axioms and rules of inference that are used to deduce tautologies and, given a set of non-logical axioms A, to deduce theorems of the theory T that is generated by A.

For instance your first challenge $(p\wedge (p\to q)\to q)$ is pretty close to the rule of inference known as Modus Ponens, which is in both (a) and (b).

Here is a list of rules that can be used in (b)
The rules of (a) are set out in this article.

 

[member 587159]

Hello. How one proves that depends on what system of logical axioms and rules of inference one is using.

If one is not using truth tables, one uses axioms and rules of inference. Two well known systems are (a) the Hilbert System and (b) Natural Deduction. Each has a set of axioms and rules of inference that are used to deduce tautologies and, given a set of non-logical axioms A, to deduce theorems of the theory T that is generated by A.

For instance your first challenge $(p\wedge (p\to q)\to q)$ is pretty close to the rule of inference known as Modus Ponens, which is in both (a) and (b).

Here is a list of rules that can be used in (b)
The rules of (a) are set out in this article.

I suppose I'm using natural deduction. Could you maybe look at the additional questions?

 

[andrewkirk]

I suppose I'm using natural deduction. Could you maybe look at the additional questions?

Those three items you've quoted in your additional questions are all valid theorems of classical logic. How they are proven depends on what axioms one starts with.