Prove NOR is Complete: Logic Problem Solved

  • Context: Graduate 
  • Thread starter Thread starter zetafunction
  • Start date Start date
  • Tags Tags
    Logic
Click For Summary
SUMMARY

The discussion focuses on proving the functional completeness of the NOR operator in logic. Participants outline the process of expressing NOT, AND, and OR operations solely using the NOR operator. By applying DeMorgan's laws, they demonstrate that NOT can be represented as NOR(NOR(x, x)), AND as NOR(NOR(x, y), NOR(x, y)), and OR as NOR(NOR(x, x), NOR(y, y)). This establishes that NOR is indeed functionally complete.

PREREQUISITES
  • Understanding of logical operators, specifically NOR.
  • Familiarity with DeMorgan's laws in logic.
  • Basic knowledge of functional completeness in Boolean algebra.
  • Experience with logical expressions and their transformations.
NEXT STEPS
  • Research the derivation of NOT using NOR in detail.
  • Explore the application of DeMorgan's laws in logical proofs.
  • Study other functional completeness proofs for different logical operators.
  • Investigate the implications of functional completeness in computer science and digital circuit design.
USEFUL FOR

Logicians, computer scientists, and students of mathematics who are interested in the foundations of logic and Boolean algebra.

zetafunction
Messages
371
Reaction score
0
how could i express using only the operator NOR (in logic) the rest of operation NOT(x) AND(x,y) OR(x,y) that is how i could prove that the Logic operator NOR is functionally complete
 
Physics news on Phys.org
See if you can figure out NOT in terms of NOR (this is not too hard), then use DeMorgan's laws to figure out how to write AND and OR using NOT and NOR.
 

Similar threads

Undergrad What Are the Axioms of Fuzzy Logic and How Do They Extend Boolean Algebra?
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad On the meaning of logical implication within specific context/models
  • · Replies 22 ·
Replies
22
Views
4K
Graduate Second-order arithmetic
  • · Replies 34 ·
2
Replies
34
Views
4K
High School Traditional logic and its usefulness in the past
  • · Replies 21 ·
Replies
21
Views
3K
Graduate Second order logic and completeness
  • · Replies 11 ·
Replies
11
Views
3K
Graduate Prove that points which are indistinguishable from 0 exist (using logic)
  • · Replies 17 ·
Replies
17
Views
3K
Graduate Prove the 2nd axiom of mathematical logic using the Deduction Theorem
  • · Replies 1 ·
Replies
1
Views
2K
Graduate What are your insights on The Hardest Logic Puzzle Ever?
  • · Replies 2 ·
Replies
2
Views
3K
High School Are Implication and Equivalence Interchangeable in Logic?
  • · Replies 9 ·
Replies
9
Views
2K
Undergrad Can you calculate the probability of a complex logic expression?
  • · Replies 3 ·
Replies
3
Views
2K