Constructing Proofs for DeMorgan's Theorem using Basic Logical Rules

  • Thread starter ghosttea
  • Start date
  • Tags
    Theorem
In summary, the individual is seeking assistance with constructing two proofs to prove that DeMorgan's is redundant for their logic homework. They are limited to using specific techniques and resources from their class and textbook. They provide two potential proofs and ask for verification or feedback.
  • #1
ghosttea
1
0
For my logic homework, I'm supposed to construct two proofs to prove that DeMorgan's is redundant. I'm not given a theorem or anything to start with.

I'm only allowed to use Modus Ponens, Modus Tollens, Hypothetical Syllogism, Simplification, COnjunction, Dilemma, Disjunctive Syllogism, Addition, Double Negation, Duplication, Commutation, Contraposition, Association, Biconditional Exchange, Conditional Exchange, Distribution, Exportation, Indirect Proof, and Conditional Proof.

Those are the only ones that we've studied in my class and the only ones that (I've noticed at least) are in the textbook (Understanding Symbolic Logic by Virginia Klenk). I'm only allowed to use Klenk's system, too.

I THINK I have one of them already, but I'm not completely positive. It feels... not quite right, but not quite wrong to me either.
1. ~A&B prem.
2. | (AvB) Assp. for I.P.
3. | ~A Simp. 1
4. | ~B Simp. 1
5. | A 2, 4 Disjunctive Syllogism
6. | (~A&A) 3, 5 conjunction
7. ~(AvB) 2-6 I.P.

I've tried looking around at the other answers for this on this forum, but none of them work for what I'm allowed to do.
 
Physics news on Phys.org
  • #2
Any help would be appreciated. Here is another proof I constructed:1. ~A & B Premise2. | (AvB) Assumption for IP3. | A Assumption for IP4. | B Assumption for IP5. | ~(~A & B) 2,3 Conjunction6. ~(AvB) 1-5 IP I believe this is valid, but if someone could verify or provide feedback that would be wonderful. Thank you.
 

1. What is DeMorgan's Theorem?

DeMorgan's Theorem is a fundamental concept in Boolean algebra that states that the complement of a union of two sets is equal to the intersection of their complements, and vice versa.

2. Why is DeMorgan's Theorem important?

DeMorgan's Theorem is important because it allows for simplification of logical expressions and helps in solving problems related to digital circuits, computer programming, and other areas that involve Boolean logic.

3. How is DeMorgan's Theorem proved?

DeMorgan's Theorem can be proved using the basic laws and rules of Boolean algebra, such as the distributive law, commutative law, and identity law. The proof involves breaking down the original expression into simpler forms and then using these laws to show that they are equivalent.

4. What are the two forms of DeMorgan's Theorem?

DeMorgan's Theorem can be expressed in two equivalent forms: the first form states that the complement of a union is equal to the intersection of complements, while the second form states that the complement of an intersection is equal to the union of complements.

5. Can DeMorgan's Theorem be extended to more than two sets?

Yes, DeMorgan's Theorem can be extended to any number of sets. The general form states that the complement of the union of multiple sets is equal to the intersection of their complements, and vice versa.

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Precalculus Mathematics Homework Help
Replies
3
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • General Discussion
Replies
2
Views
5K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
3
Views
5K
  • General Discussion
Replies
2
Views
3K
Back
Top