- #1
ranjha
- 5
- 0
Can someone tell me how to prove DeMorgan's Laws using the basic rules?
~(A & B) = ~A v ~B
Please help
~(A & B) = ~A v ~B
Please help
Well, you are given no premises, so you will have to use conditional proof or reductio, right?ranjha said:This is homework...we are expected to know this. It's just that we have been taught a certain number of rules of inference. So the examples I have seen don't make sense to me. We have to know how to prove his Law by using the rules we have learned: Modus Ponens, Tollens, Simplification, Conjunction, Disjunction, Conjunctive and Disjunctive Arguments, Conditional Proofs, Chain Rule, Dilemmas, Reductio, Double Negation, Transposition, and Material Implication. These are the only ones we have learned so far and I am completely lost as to how to start. Please help.
Yes, that's what I meant.ranjha said:ok:
1) ~A v ~B (assume)
2)) A & B (assume)
3)) A --> ~B (1 M Implication)
is this what you mean?? but where do I go from here?
That's right, except that I forgot to nest the first assumption.ranjha said:ok I kind of understand what you are trying to do. I get that you are going to use Reductio to prove the law. But can you please get me started? I don't know what the next step should be.
1) ~A v ~B (assume)
2)) A & B (assume)
3)) A --> ~B (1 M Implication)
4)) A (2 simplification)
5)) ~B (3,4 MP)
6)) B (2 simplification)
7)) B & ~B (5,6 Conjunction)
DeMorgan's Laws are a set of rules in boolean algebra that describe the relationship between logical operators "AND" and "OR". They state that the negation of a conjunction (AND) is equivalent to the disjunction (OR) of the negations of the individual terms, and vice versa.
Augustus De Morgan, a British mathematician and logician, first described DeMorgan's Laws in the 19th century. However, other mathematicians, such as Leibniz and Boole, had previously hinted at similar concepts.
DeMorgan's Laws are important because they allow us to simplify boolean expressions and make them easier to work with. They also help us to understand the logical relationships between different statements and expressions.
In computer science, DeMorgan's Laws are used to manipulate and simplify boolean expressions in programming languages and digital logic circuits. They are particularly useful in optimizing code and improving the efficiency of computer systems.
Yes, DeMorgan's Laws can be applied to any logical operator that has an inverse, such as "NOT" and "NOR". They can also be extended to multiple variables and more complex boolean expressions.