1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Question about the possible non equivalent logical statements

  1. Sep 27, 2011 #1
    1. The problem statement, all variables and given/known data

    I'm trying to figure out how many unique (non-equivalent) logical statements are possible with n statements...I think I could figure that out as soon as I see a pattern so I would like to know how many are possible for 2 statements and for 3 statements

    2. Relevant equations



    3. The attempt at a solution
    I know that for 1 statement there are two possibilities, namely, P and ~p. I think for two there are twelve possibilities: P,Q,~P,~Q, PVQ, P^Q, ~(PVQ),~(P^Q),P=>Q,Q=>P,Q<=>P,~(Q<=>P)..are those all the possibilities for 2 statements?
     
  2. jcsd
  3. Sep 27, 2011 #2

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    I think you mean the number of inequivalent statements containing n logical variables, right? Think about the number of possible ways to fill out a truth table.
     
  4. Sep 27, 2011 #3
    Hey its you! :)
    uhh yes I think...like for n=3 it would be the statements P,Q, R and all the possible ways that they are connected..
    I know that a truth table can be filled out 2^n ways..like that's how many rows there will be in the truth table
     
  5. Sep 27, 2011 #4

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Right. Now how many ways can you fill out the truth of the statement entry in the truth table?? For each line in the truth table you can write T or F, right?
     
  6. Sep 27, 2011 #5
    yep so....its......2^n*(2^n)?..is it like if u have a true false test of say..ten questions then you have 2^10 different possibilities?..but this time the number of rows are 2^n
     
  7. Sep 27, 2011 #6
    no wait...its 2^(2^n)
     
  8. Sep 27, 2011 #7

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Yes. You don't have to write out explicit statements for each case to know how many there are.
     
  9. Sep 27, 2011 #8
    wait ....does that mean that for n=1 there's 2^2=4 different possibilities..I thought there was only 1 (P and ~P)
     
  10. Sep 27, 2011 #9

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    There are four. P, ~P, T and F. Or P, ~P, (P and ~P) and (P or ~P) if you prefer. See?
     
  11. Sep 27, 2011 #10
    AHH I see I didnt think about that!..but are (P and ~P) and (P or ~P) logically...valid? like what do they mean..do such things exist ..such that (P and ~P) for example
     
  12. Sep 27, 2011 #11

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Of course they exist. (P or ~P) or (P V ~P) is always true. Isn't it? What about (P and ~P)?
     
  13. Sep 27, 2011 #12
    hmm the truth table would be:
    P Q P^Q
    T F F
    F T F

    So P^Q is false all the time...I guess that makes sense because u cant have something and "not something" at the same time
     
  14. Sep 27, 2011 #13

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    It's just like any other logical statement. It just happens to be false all the time. It's the opposite of a tautology.
     
  15. Sep 27, 2011 #14
    ooo..a contradiction? Thank-you so much again! Haha I wish you were my teacher!!!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook