How to prove De Morgan's theorems with propositional logic?
Hello. I spent some time trying to prove the validity of De Morgan's theorems in propositional logic by direct proof and reductio ad absurdum, but I couldn't do the demonstration without assuming that they are already valid, which would be a circular reasoning. Does anyone know how to do this? I know it's easy to do it using truth tables, but I'd like to do this based on other rules of inference. Thank you all!
1'st De Morgan Theorem: ¬(P?Q)?(¬P?¬Q)
2'st De Morgan Theorem: ¬(P?Q)?(¬P?¬Q)
1'st De Morgan Theorem: ¬(P?Q)?(¬P?¬Q)
2'st De Morgan Theorem: ¬(P?Q)?(¬P?¬Q)
Comments (12)
1. ~(PvQ)
2. Assume P.
3. PvQ (2, disjunction introduction)
4. ~P (1,2,3, contradiction).
Repeat for Q, though it might just give you the => implication. In case that's true, something like:
1: ~P and ~Q
2. Assume P v Q
3. Assume P
4. ~P from contradiction
5. Assume Q
6. ~Q from contradiction
7. ~(P v Q)
would probably work for the <=.
For 2.
1. ~P or ~Q
2. Assume P & Q
3. Assume P
4. ~Q (disjunctive syllogism, 3,1)
5. Assume Q
6. ~P (disjunctive syllogism, 4,1)
7. ~(P & Q) (2, contradiction)
Same qualifying remark for the reverse implication - this might not be a reversible proof.
I don't know if these strategies are actually valid in the logic you're working in, but perhaps they might inspire you to find a strategy which works.
For 1:
For 2:
I've seen another way to express this with :: as in ~(p v q) :: ~p & ~q
What's the difference between double implication (<=>) and logical equivalence (::)?
On the other hand, if two sentences P and Q are logically equivalent, then they express the same logical truth (and therefore have the same truth value), and one of them can be substituted by the other without problem. I don't know if it is right, but the difference seems, for me, to be a semantical one. Do you know the difference, or some book or paper that explains more about this? Thanks for the comment!
Propositional and first order predicate logic both have the deduction metatheorem. They also have the property of completeness, so that semantic entailment (truth tables or tableaux) and syntactic entailment (proofs in the logics using the inference rules) are equivalent.
A double implication like P <-> Q is true when both P and Q have the same truth values in a truth table.
Two propositions P and Q are logically equivalent iff they have the same truth values in a truth table.
They're the same thing, since propositional logic is complete and has the deduction theorem.
You just have to be careful with what those iffs work like. It's true in propositional logic that If P=>Q this yields P |- Q and P |=Q, but the 'this yields' isn't the same thing as material implication. Saying P |- Q (syntactic derivation) <=> P |= Q (semantic derivation) can be flat out wrong since the <=> biconditional is syntactic. When you're dealing with languages and metalanguages at the same time it pays to be careful with your symbols.
First order logic is logic with quantification over variables. It's an expansion of propositional (or zeroth order) logic. It's been a while since I studied logic, but I can recommend the book 'Logic with Trees', it goes through propositional and first order logic thoroughly and includes some stuff on soundness/completeness/other things in meta-logic. Lots of exercises too.