Results 1 to 5 of 5

Math Help - Tautologies

  1. #1
    Newbie
    Joined
    Sep 2012
    From
    Cali
    Posts
    2

    Lightbulb Tautologies

    Heres what I know, I know what a tautology is, I know what it looks like from looking at a truth table. Heres what i need help with, how do i prove these are tautologies, just truth tables alone?(also how would i set these up in a truth table) or are there other methods i could use. I only got a little past using truth tables in my book so id probably feel more comfortable using those.
    a) 段 ^ p -> q -> 殆
    b) p V q ^ 殆 -> q
    ( ^ is supposed to be the upside down V)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Tautologies

    To start, could you clarify the syntactic conventions? It is usually assumed that implication associates to the right, i.e., 段 /\ p -> q -> 殆 is 段 /\ p -> (q -> 殆). I also assume that /\ binds stronger than \/, i.e., p \/ q /\ 殆 -> q is p \/ (q /\ 殆) -> q.

    Quote Originally Posted by KellyFay View Post
    how do i prove these are tautologies, just truth tables alone?
    Yes, or some modification of the truth table method.

    Quote Originally Posted by KellyFay View Post
    (also how would i set these up in a truth table)
    If you know how to construct truth tables, then you should be able to do this for these formulas. Otherwise, what exactly is your question about truth tables?

    Quote Originally Posted by KellyFay View Post
    are there other methods i could use.
    It is sometimes easier to try to find a falsifying assignment (valuation, interpretation). For example, if 段 /\ p -> (q -> 殆) is false, then 段 /\ p is true and (q -> 殆) is false, which means that q is true and 殆 is false. From the last two facts, both p and q are true, but then 段 /\ p is not true. Since there is no falsifying assignment, the formula is a tautology.

    There is a falsifying assignment for p \/ (q /\ 殆) -> q, but not for (p \/ q) /\ 殆 -> q.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539

    Re: Tautologies

    Hello, KellyFay!

    Could you replace the parentheses?
    I'm sure that the problems weren't give to you this way . . .


    (a)\;\sim q \wedge  p \to q \to \;\sim p

    (b)\;p \vee q \:\wedge \sim p  \to  q

    \sim\!q \wedge p \to q \to \;\sim\!p can be interpreted in a number of ways:

    . . \big[(\sim\!q \wedge p) \to q\big] \to\; \sim\!p

    . . (\sim\!q \wedge p) \to (q\to\; \sim\!p)

    . . \big[\sim\!q \wedge (p \to q)\big] \to \sim\!p

    . . \sim\!q \wedge \big[(p\to q) \to\; \sim\!p\big]

    . . \sim q \wedge \big[p \to (q \to\; \sim\!p)\big]

    . . \sim\big[(q \wedge p) \to (q \to \sim\!p)\big]

    . . . . . . . . .etc.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,547
    Thanks
    539

    Re: Tautologies


    Since KellyFay has not returned, I guessed what her problems were.


    (a)\;(\sim\!q \wedge p) \to (q \to \:\sim\!p)

    \begin{array}{|c|c||c|c|c|c|c|c|c|} p&q&(\sim\!q & \wedge & p) & \to & (q & \to & \sim\!p) \\ \hline T&T& F&F&T& {\color{red}T} & F&F&F \\ T&F & T&T&T & {\color{red}T} & F&T&T \\ F&T & F&F&F & {\color{red}T} & T&T&T \\ F&F & T&F&F & {\color{red}T} & F&T&T \\ \hline && 1 & 2 & 1 & 3 & 1 & 2 & 1 \\ \hline \end{array}




    (b)\;\big[(p \vee q) \:\wedge \sim\!p \big] \to q

    \begin{array}{|c|c||c|c|c|c|c|c|c|} p&q & [(p & \vee & q) & \wedge & \sim\!p] & \to & q \\ \hline T&T & T&T&T& F & F & {\color{red}T} & T \\ T&F & T&T&F & F & F & {\color{red}T} & F \\ F&T & F&T&T& T & T & {\color{red}T} & T \\ F&F & F&F&F & F & T & {\color{red}T} & T \\ \hline &&1&2&1&3&1&4&1 \\ \hline \end{array}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Sep 2012
    From
    Washington DC USA
    Posts
    525
    Thanks
    146

    Re: Tautologies

    That's a lot of work!
    Thanks (I like the numbering scheme on the bottom row - is that a standard practice?)
    It doesn't change the tautology, but I think there are two incorrect entries in the top diagram. (They look like transcription errors, because you then produced a correct result based not on what's showing, but on what should be showing - if I'm following you correctly.)
    Top diagram, top row, 3rd column from the right (under the "q"): I think it should be a T.
    Top diagram, 2nd row, rightmost column (under the "~p"): I think it should be an F.
    Oh - and I think I see one more:
    Bottom diagram, bottom row, rightmost column(under the "q"): I think it should be an F .
    Last edited by johnsomeone; September 27th 2012 at 09:13 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof for Tautologies uisng equations
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: October 11th 2011, 02:35 AM
  2. Replies: 8
    Last Post: July 6th 2011, 01:47 PM
  3. Tautologies
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 13th 2010, 01:26 PM
  4. Tautologies
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 10th 2007, 03:38 AM

Search Tags


/mathhelpforum @mathhelpforum