Natural Deduction

  • Thread starter StarThrower
  • Start date
  • Tags
    Natural
In summary, the conversation discusses the limitations on the number of undefined logical operators, with the suggestion of using only {not,and} or {not,or}. The concept of building any binary operator out of just nand is also mentioned. The meaning of "nand" is clarified, and it is noted that NOR can also be used in place of NAND.
  • #1
StarThrower
220
1
Does anyone know a set of axioms for natural deductions? One which leads to the rest of the tautologies of the propositional calculus (and,or,not,if,iff) as theorems?

I want the number of undefined logical operators to be limited to two, either {not,and} or {not,or}.
 
Physics news on Phys.org
  • #2
Originally posted by StarThrower


I want the number of undefined logical operators to be limited to two, either {not,and} or {not,or}.
if I am not mistaken those logical operators are defined if they weren't then how could we use them?
 
  • #3
For the record, you can build any binary operator out of just nand.
 
  • #4
what does nand mean?
 
  • #5
Originally posted by loop quantum gravity
what does nand mean?

"Not And". It's the negation of the AND relation. The point being that, I believe it has been proven that any digital circuit you can make with the normal boolean operators you can make with NAND gates. Is that right?
 
  • #6
[tex]\begin{align*}
!A&=A\barwedge A \\
A\wedge B&=(A\barwedge B)\barwedge(A\barwedge B) \\
A\vee B&=(A\barwedge A)\barwedge(A\barwedge B)
\end{align*}[/tex]

For those less familiar with such notation, [itex]!,\wedge,\vee,\barwedge[/itex] mean NOT, AND, OR and NAND, respectively.

So you can clearly express NOT, AND and OR using just NAND.
 
  • #7
Hurkyl said:
For the record, you can build any binary operator out of just nand.


"NOR" suffices as well.
 

What is natural deduction?

Natural deduction is a formal system of logic that uses rules and principles to prove the validity of arguments. It is a deductive approach to reasoning that is based on the idea that the truth of a conclusion can be derived from the truth of its premises.

What are the basic rules of natural deduction?

The basic rules of natural deduction include the rules of inference, which allow you to derive new conclusions from given premises, and the rules of replacement, which allow you to substitute equivalent statements in an argument. Some common rules of inference include modus ponens, modus tollens, and disjunctive syllogism.

What is the difference between natural deduction and other methods of proof?

Natural deduction differs from other methods of proof, such as truth tables and axiomatic systems, in that it is more intuitive and closely resembles the way humans reason. It also allows for more flexibility and creativity in constructing proofs.

How is natural deduction used in scientific research?

Natural deduction is used in scientific research to construct and analyze logical arguments and to test the validity of hypotheses. It helps scientists to think critically and systematically about their ideas and to identify any flaws or inconsistencies in their reasoning.

What are some common applications of natural deduction?

Natural deduction has a wide range of applications in fields such as mathematics, philosophy, computer science, and linguistics. It is used to prove theorems, solve problems, and analyze arguments in these disciplines. It is also commonly used in education to teach students how to think logically and to construct valid arguments.

Similar threads

Replies
8
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
11
Views
2K
Replies
13
Views
1K
  • Programming and Computer Science
Replies
4
Views
1K
  • Quantum Interpretations and Foundations
Replies
15
Views
2K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
3K
Replies
72
Views
4K
  • General Discussion
2
Replies
43
Views
4K
  • General Discussion
Replies
12
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
10
Views
1K
Back
Top