# I P ^ (p -> q) => q proof

Tags:
1. Sep 8, 2016

### Math_QED

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$

2. Sep 8, 2016

### 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)

3. Sep 11, 2016

### Math_QED

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

4. Sep 11, 2016

### andrewkirk

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.