Infinite logic

  • Thread starter danne89
  • Start date
  • #1
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.
 

Answers and Replies

  • #2
honestrosewater
Gold Member
2,132
5
"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
180
0
Thanks! You clear a few questionmarks, but created even more. I'll read a book on mathematical logic in the future i think.
 
  • #4
1,605
2
Try googling "infinitary logic."
 
  • #5
honestrosewater
Gold Member
2,132
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.
 

Related Threads on Infinite logic

Replies
255
Views
21K
  • Last Post
Replies
14
Views
2K
  • Last Post
Replies
4
Views
7K
  • Last Post
2
Replies
25
Views
3K
  • Last Post
Replies
10
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
3
Views
3K
  • Last Post
Replies
11
Views
3K
Top