Proving a Logical Statement: Puzzling Over Proving Pb and Not P1...

  • Thread starter danne89
  • Start date
In summary, the conversation discusses a problem with proving a logical statement and the use of infinite formulas in formal language L. The speaker asks for help in understanding how to express a formula of infinite length and how to prove the associative and commutative properties of the connective symbol "&". The expert explains the definitions of formulas and truth-valuations in L and how to prove these properties using them. They also recommend reading books on infinitary logic and mathematical logic for further understanding.
  • #1
danne89
180
0
Hi! I've problem proving a logical statement. I really can nothing about logic. I just messing around with some in a try to prove another theorem.

Anyway, I would be useful to be able to prove that:
([itex]P_b[/itex] and not [itex]P_1[/itex]) and ([itex]P_b[/tex] and not [itex]P_2[/tex] and ...
as P1, P2, P3 ...
equals Pb and not (P1, P2, P3 ...)

I don't know if this is the proper way to express this, but I hope you will get my point. If not ask. And please correct me.
 
Mathematics news on Phys.org
  • #2
"Pb and not (P1, P2, P3 ...)" would be a formula of infinite length, and I don't know of any language that allows formulas of infinite length. However, you can have an infinite set of formulas of finite length- which I suppose would work just as well.
For your proof, the setup isn't fun, but here goes.
The primitive symbols of formal language L fall into two disjoint sets: a countably infinite set of propositional symbols and a set of two distinct connective symbols, "NOT" denoted by ~ and "AND" denoted by &.
Formulas are defined as follows:
1) a propositional symbol is a formula.
2) If P is a formula, then ~P is a formula.
3) If P and Q are formulas, then &PQ is a formula.
A (truth-)valuation V on L is a mapping from the set of formulas to the set {T, F} of (truth-)values, defined as follows:
1) If P is a propositional symbol, Pv denotes the value assigned to P by V (Pv = T or Pv = F).
2) If P is a formula, (~P)v = {T if Pv = F, F if Pv = T}.
3) If P and Q are formulas, (&PQ)v = {T if Pv = T and Qv = T, F otherwise}.
You want to prove that & has the associative and commutative properties. Informally, this is simple. Say that two formulas P and Q are equivalent iff Pv = Qv for every V. So you want to prove that if R, S, and T are formulas, then (&R&ST)v = (&&RST)v and (&RS)v = (&SR)v for every V. This follows immediately from the definitions.
You also want to prove that (&PP)v = Pv (so you can get rid of all those extra Pbs). If Pv = T, then (&PP)v = T, and vice versa. If Pv = F, then (&PP)v = F, and vice versa. So they're equivalent.
We can write "&PQ" as "P & Q" and introduce parentheses and subscripts for convenience. I think the meaning of your original statement is clear, if stated as follows:
For any n in N, [(P1 & ~P2) & (P1 & ~P3) & ... & (P1 & ~Pn)] is equivalent to [P1 & (~P2 & ~P3 & ... & ~Pn)].

Note that you cannot write ~(P2, P3, ..., Pn), unless you say what the commas mean. Note also that ~(P2 & P3 & ... & Pn) is not equivalent to (~P2 & ~P3 & ... & ~Pn)- "~" doesn't distribute that way.
If that didn't help, just say so. Is that what you wanted to say?
 
  • #3
Thanks! You clear a few questionmarks, but created even more. I'll read a book on mathematical logic in the future i think.
 
  • #4
Try googling "infinitary logic."
 
  • #5
danne89 said:
Thanks! You clear a few questionmarks, but created even more.
If you have questions, just ask. :smile:
I'll read a book on mathematical logic in the future i think.
The best book on logic I've ever read is "Logic" by Wilfrid Hodges. If you read no other book on logic, read this one- Hodges is hysterical and seriously knows his stuff. You should also read this before any mathematical logic book. After that, "Set theory, logic, and their limitations" by Moshé Machover is great. "Mathematical Logic" by Joseph Shoenfield is also good.
 

1. How is a logical statement proven?

A logical statement is proven by using a series of logical steps and rules to show that the statement is true. This is usually done by starting with known, accepted statements and using logical reasoning to arrive at the conclusion of the statement being proven.

2. What are some common techniques for proving a logical statement?

Some common techniques for proving a logical statement include direct proof, proof by contradiction, proof by induction, and proof by contrapositive. These techniques involve using different methods of logical reasoning to show that the statement is true.

3. Can a logical statement be proven to be false?

No, a logical statement cannot be proven to be false. If a statement is proven to be false, it is not a logical statement. A logical statement is one that is based on accepted rules of logic and is either true or false.

4. How do you know when a logical statement has been successfully proven?

A logical statement is considered successfully proven when all the logical steps and rules used to arrive at the conclusion have been clearly and accurately shown. This means that the statement has been proven to be true using accepted methods of logical reasoning.

5. Are there any limitations to proving a logical statement?

Yes, there are some limitations to proving a logical statement. One limitation is that the statement must be based on accepted rules of logic. If the statement is not logical, it cannot be proven. Additionally, some statements may be too complex or abstract to be proven using current methods of logical reasoning.

Similar threads

  • Calculus and Beyond Homework Help
Replies
3
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Precalculus Mathematics Homework Help
Replies
11
Views
2K
  • Precalculus Mathematics Homework Help
Replies
2
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
6
Views
2K
  • Introductory Physics Homework Help
Replies
6
Views
2K
  • Special and General Relativity
2
Replies
40
Views
2K
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Calculus and Beyond Homework Help
Replies
1
Views
671
Back
Top