Understanding Post's Theorem in Propositional Calculus

  • Thread starter Goldenwind
  • Start date
  • Tags
    Calculus
In summary, the conversation is about the confusion surrounding Post's Theorem and its application in different problems. The speaker is struggling to understand the theorem and its relationship to other concepts. They are seeking a simple explanation of Post's Theorem and its significance.
  • #1
Goldenwind
146
0
Can someone explain to me what the heck Post's Theorem is? Every time my professor does something that seems to make absolutely no sense, he sites his method as "Post". I've compared the various times he uses Post, and there seems to be no pattern. I'm beginning to think that he just uses it to excuse something he wants to make it (I know this isn't true, but seems like it).

I've tried looking it up. Both the textbook and wikipedia just give a tonne more symbols that I don't understand.

Cut rule, for example, is simple: |- A -> B becomes A |- B
Can someone lay out Post simply like that? :(
 
Physics news on Phys.org
  • #2
'kay. This is all in studying for my exam, which is in about 17 hours, so I'll be a bit more specific.

http://www.cse.yorku.ca/~gt/courses/MATH1090F07/asg4-sol.pdf

The first problem that is shown uses Post to demonstrate that if you have A -> (B=C) and A -> B, then A -> C due to the fact that B and C must have the same value. I understand this. Is this rule called "Post"? Maybe. Take a look in future questions.

The second problem uses "Post" to demonstrate that (A v B) -> C is the same thing as A -> C. Not only does this not make sense to me, it also seems to have nothing to do with the "Post" theorem that we used in the first problem. Why is this true, and what does the "Post" theorem really mean?
 
Last edited by a moderator:

What is propositional calculus?

Propositional calculus is a branch of mathematical logic that deals with the study of propositions, which are statements that can either be true or false. It aims to analyze the logical relationships between propositions and determine the validity of arguments.

What are the basic components of propositional calculus?

The basic components of propositional calculus are propositions, logical connectives, and quantifiers. Propositions are statements that can be either true or false. Logical connectives, such as "and", "or", and "not", are used to combine propositions and create more complex statements. Quantifiers, such as "for all" and "there exists", are used to express the generality of propositions.

What is the difference between propositional calculus and predicate calculus?

Propositional calculus deals with propositions that are either true or false, while predicate calculus deals with propositions that involve variables and can take on different truth values depending on the values assigned to the variables. Predicate calculus is more expressive and can handle more complex statements than propositional calculus.

How is propositional calculus used in computer science?

Propositional calculus is used in computer science to represent and reason about the truth values of statements in computer programs. It is also used in formal verification to prove the correctness of programs and in artificial intelligence for automated reasoning.

What are some practical applications of propositional calculus?

Propositional calculus has many practical applications, such as in digital circuit design, where it is used to model and analyze the behavior of logic gates. It is also used in decision-making systems, such as expert systems, to represent and reason about knowledge and rules. Additionally, propositional calculus is used in database systems for query optimization and in the field of linguistics for analyzing the structure of natural language sentences.

Similar threads

  • STEM Academic Advising
Replies
9
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
  • Science and Math Textbooks
Replies
17
Views
2K
  • Science and Math Textbooks
Replies
12
Views
2K
  • STEM Academic Advising
2
Replies
45
Views
4K
Replies
25
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
1K
  • Calculus and Beyond Homework Help
Replies
2
Views
2K
  • Calculus and Beyond Homework Help
Replies
4
Views
1K
  • Calculus and Beyond Homework Help
Replies
4
Views
2K
Back
Top