Propositional Logic - Equivalences [on hold]

Clash Royale CLAN TAG#URR8PPP

up vote
0
down vote

favorite

I just started logic and am having trouble working through it.

Can somebody show, step by step, how the following formulas are equivalent? I.e.

$(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow requiv (q rightarrow r)$

Thank you so much!

logic propositional-calculus

share|cite|improve this question

edited Aug 3 at 14:39

zzuussee

1,101419

asked Aug 3 at 14:03

Jennifer Greene

31

put on hold as off-topic by Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen 2 days ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you know about truth tables?
  – fosho
  Aug 3 at 14:05
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

I just started logic and am having trouble working through it.

Can somebody show, step by step, how the following formulas are equivalent? I.e.

$(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow requiv (q rightarrow r)$

Thank you so much!

logic propositional-calculus

share|cite|improve this question

edited Aug 3 at 14:39

zzuussee

1,101419

asked Aug 3 at 14:03

Jennifer Greene

31

put on hold as off-topic by Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen 2 days ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you know about truth tables?
  – fosho
  Aug 3 at 14:05
  

  
  
  
  

add a comment | 

up vote
0
down vote

favorite

up vote
0
down vote

favorite

I just started logic and am having trouble working through it.

Can somebody show, step by step, how the following formulas are equivalent? I.e.

$(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow requiv (q rightarrow r)$

Thank you so much!

logic propositional-calculus

share|cite|improve this question

edited Aug 3 at 14:39

zzuussee

1,101419

asked Aug 3 at 14:03

Jennifer Greene

31

I just started logic and am having trouble working through it.

Can somebody show, step by step, how the following formulas are equivalent? I.e.

$(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow requiv (q rightarrow r)$

Thank you so much!

logic propositional-calculus

share|cite|improve this question

edited Aug 3 at 14:39

zzuussee

1,101419

asked Aug 3 at 14:03

Jennifer Greene

31

share|cite|improve this question

share|cite|improve this question

edited Aug 3 at 14:39

zzuussee

1,101419

edited Aug 3 at 14:39

zzuussee

1,101419

edited Aug 3 at 14:39

zzuussee

1,101419

1,101419

asked Aug 3 at 14:03

Jennifer Greene

31

asked Aug 3 at 14:03

Jennifer Greene

31

asked Aug 3 at 14:03

Jennifer Greene

31

31

put on hold as off-topic by Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen 2 days ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen

If this question can be reworded to fit the rules in the help center, please edit the question.

put on hold as off-topic by Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen 2 days ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Adrian Keister, Xander Henderson, Taroccoesbrocco, amWhy, Jyrki Lahtonen

If this question can be reworded to fit the rules in the help center, please edit the question.

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you know about truth tables?
  – fosho
  Aug 3 at 14:05
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  Do you know about truth tables?
  – fosho
  Aug 3 at 14:05
  

  
  
  
  

1

1

Do you know about truth tables?
– fosho
Aug 3 at 14:05

Do you know about truth tables?
– fosho
Aug 3 at 14:05

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote



accepted

I assume that you are working in classical propositional logic. Two formulas $phi$ and $psi$ are equivalent(semantically) iff they have the same truth-values under every interpretation of the variables.

I also assume that by $(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow r$ you mean $(neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)$

We might check this condition by building a so called truth table to list all the possible variants of such a mapping:

beginarrayc
hline
p& q& r & qrightarrow r & neg qrightarrowneg p & neg qrightarrow p & (neg qrightarrow p)rightarrow r & (neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)\ hline
0& 0& 0& 1& 1& 0& 1& 1\ hline
0& 0& 1& 1& 1& 0& 1& 1\ hline
0& 1& 0& 0& 1& 1& 0& 0\ hline
0& 1& 1& 1& 1& 1& 1& 1\ hline
1& 0& 0& 1& 0& 1& 0& 1\ hline
1& 0& 1& 1& 0& 1& 1& 1\ hline
1& 1& 0& 0& 1& 1& 0& 0\ hline
1& 1& 1& 1& 1& 1& 1& 1\ hline
endarray

Note that I've added some extra columns to make the calculations more clear. You only need to compare the 4-th and the last column for equivalence.

It is a good training in truth tables to construct this one yourself. Maybe check in the truth tables of the standard operators $rightarrow$ and $neg$ and try it yourself.

EDIT: A little note on why it suffices to check that they have the same truth value under every interpretation.

Two formulas $phi$ and $psi$ are equivalent if $modelsphileftrightarrowpsi$, that is if $phileftrightarrowpsi=phirightarrowpsilandpsirightarrowphi$ is a tautology, i.e. it is always true.

Now, you can check by the semantic evaluation of $rightarrow$ and $land$(the corresponding truth tables), that given an assignment of truth values(an interpretation) $mathcalI$, that $mathcalI(phileftrightarrowpsi)$=1 iff $mathcalI(phi)=mathcalI(psi)$.

share|cite|improve this answer

edited Aug 3 at 14:25

answered Aug 3 at 14:20

zzuussee

1,101419

add a comment | 

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote



accepted

I assume that you are working in classical propositional logic. Two formulas $phi$ and $psi$ are equivalent(semantically) iff they have the same truth-values under every interpretation of the variables.

I also assume that by $(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow r$ you mean $(neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)$

We might check this condition by building a so called truth table to list all the possible variants of such a mapping:

beginarrayc
hline
p& q& r & qrightarrow r & neg qrightarrowneg p & neg qrightarrow p & (neg qrightarrow p)rightarrow r & (neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)\ hline
0& 0& 0& 1& 1& 0& 1& 1\ hline
0& 0& 1& 1& 1& 0& 1& 1\ hline
0& 1& 0& 0& 1& 1& 0& 0\ hline
0& 1& 1& 1& 1& 1& 1& 1\ hline
1& 0& 0& 1& 0& 1& 0& 1\ hline
1& 0& 1& 1& 0& 1& 1& 1\ hline
1& 1& 0& 0& 1& 1& 0& 0\ hline
1& 1& 1& 1& 1& 1& 1& 1\ hline
endarray

Note that I've added some extra columns to make the calculations more clear. You only need to compare the 4-th and the last column for equivalence.

It is a good training in truth tables to construct this one yourself. Maybe check in the truth tables of the standard operators $rightarrow$ and $neg$ and try it yourself.

EDIT: A little note on why it suffices to check that they have the same truth value under every interpretation.

Two formulas $phi$ and $psi$ are equivalent if $modelsphileftrightarrowpsi$, that is if $phileftrightarrowpsi=phirightarrowpsilandpsirightarrowphi$ is a tautology, i.e. it is always true.

Now, you can check by the semantic evaluation of $rightarrow$ and $land$(the corresponding truth tables), that given an assignment of truth values(an interpretation) $mathcalI$, that $mathcalI(phileftrightarrowpsi)$=1 iff $mathcalI(phi)=mathcalI(psi)$.

share|cite|improve this answer

edited Aug 3 at 14:25

answered Aug 3 at 14:20

zzuussee

1,101419

add a comment | 

up vote
2
down vote



accepted

I assume that you are working in classical propositional logic. Two formulas $phi$ and $psi$ are equivalent(semantically) iff they have the same truth-values under every interpretation of the variables.

I also assume that by $(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow r$ you mean $(neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)$

We might check this condition by building a so called truth table to list all the possible variants of such a mapping:

beginarrayc
hline
p& q& r & qrightarrow r & neg qrightarrowneg p & neg qrightarrow p & (neg qrightarrow p)rightarrow r & (neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)\ hline
0& 0& 0& 1& 1& 0& 1& 1\ hline
0& 0& 1& 1& 1& 0& 1& 1\ hline
0& 1& 0& 0& 1& 1& 0& 0\ hline
0& 1& 1& 1& 1& 1& 1& 1\ hline
1& 0& 0& 1& 0& 1& 0& 1\ hline
1& 0& 1& 1& 0& 1& 1& 1\ hline
1& 1& 0& 0& 1& 1& 0& 0\ hline
1& 1& 1& 1& 1& 1& 1& 1\ hline
endarray

Note that I've added some extra columns to make the calculations more clear. You only need to compare the 4-th and the last column for equivalence.

It is a good training in truth tables to construct this one yourself. Maybe check in the truth tables of the standard operators $rightarrow$ and $neg$ and try it yourself.

EDIT: A little note on why it suffices to check that they have the same truth value under every interpretation.

Two formulas $phi$ and $psi$ are equivalent if $modelsphileftrightarrowpsi$, that is if $phileftrightarrowpsi=phirightarrowpsilandpsirightarrowphi$ is a tautology, i.e. it is always true.

Now, you can check by the semantic evaluation of $rightarrow$ and $land$(the corresponding truth tables), that given an assignment of truth values(an interpretation) $mathcalI$, that $mathcalI(phileftrightarrowpsi)$=1 iff $mathcalI(phi)=mathcalI(psi)$.

share|cite|improve this answer

edited Aug 3 at 14:25

answered Aug 3 at 14:20

zzuussee

1,101419

add a comment | 

up vote
2
down vote



accepted

up vote
2
down vote



accepted

I assume that you are working in classical propositional logic. Two formulas $phi$ and $psi$ are equivalent(semantically) iff they have the same truth-values under every interpretation of the variables.

I also assume that by $(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow r$ you mean $(neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)$

We might check this condition by building a so called truth table to list all the possible variants of such a mapping:

beginarrayc
hline
p& q& r & qrightarrow r & neg qrightarrowneg p & neg qrightarrow p & (neg qrightarrow p)rightarrow r & (neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)\ hline
0& 0& 0& 1& 1& 0& 1& 1\ hline
0& 0& 1& 1& 1& 0& 1& 1\ hline
0& 1& 0& 0& 1& 1& 0& 0\ hline
0& 1& 1& 1& 1& 1& 1& 1\ hline
1& 0& 0& 1& 0& 1& 0& 1\ hline
1& 0& 1& 1& 0& 1& 1& 1\ hline
1& 1& 0& 0& 1& 1& 0& 0\ hline
1& 1& 1& 1& 1& 1& 1& 1\ hline
endarray

Note that I've added some extra columns to make the calculations more clear. You only need to compare the 4-th and the last column for equivalence.

It is a good training in truth tables to construct this one yourself. Maybe check in the truth tables of the standard operators $rightarrow$ and $neg$ and try it yourself.

EDIT: A little note on why it suffices to check that they have the same truth value under every interpretation.

Two formulas $phi$ and $psi$ are equivalent if $modelsphileftrightarrowpsi$, that is if $phileftrightarrowpsi=phirightarrowpsilandpsirightarrowphi$ is a tautology, i.e. it is always true.

Now, you can check by the semantic evaluation of $rightarrow$ and $land$(the corresponding truth tables), that given an assignment of truth values(an interpretation) $mathcalI$, that $mathcalI(phileftrightarrowpsi)$=1 iff $mathcalI(phi)=mathcalI(psi)$.

share|cite|improve this answer

edited Aug 3 at 14:25

answered Aug 3 at 14:20

zzuussee

1,101419

I assume that you are working in classical propositional logic. Two formulas $phi$ and $psi$ are equivalent(semantically) iff they have the same truth-values under every interpretation of the variables.

I also assume that by $(neg qrightarrowneg p)rightarrow (neg qrightarrow p)rightarrow r$ you mean $(neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)$

We might check this condition by building a so called truth table to list all the possible variants of such a mapping:

beginarrayc
hline
p& q& r & qrightarrow r & neg qrightarrowneg p & neg qrightarrow p & (neg qrightarrow p)rightarrow r & (neg qrightarrowneg p)rightarrow ((neg qrightarrow p)rightarrow r)\ hline
0& 0& 0& 1& 1& 0& 1& 1\ hline
0& 0& 1& 1& 1& 0& 1& 1\ hline
0& 1& 0& 0& 1& 1& 0& 0\ hline
0& 1& 1& 1& 1& 1& 1& 1\ hline
1& 0& 0& 1& 0& 1& 0& 1\ hline
1& 0& 1& 1& 0& 1& 1& 1\ hline
1& 1& 0& 0& 1& 1& 0& 0\ hline
1& 1& 1& 1& 1& 1& 1& 1\ hline
endarray

Note that I've added some extra columns to make the calculations more clear. You only need to compare the 4-th and the last column for equivalence.

It is a good training in truth tables to construct this one yourself. Maybe check in the truth tables of the standard operators $rightarrow$ and $neg$ and try it yourself.

EDIT: A little note on why it suffices to check that they have the same truth value under every interpretation.

Two formulas $phi$ and $psi$ are equivalent if $modelsphileftrightarrowpsi$, that is if $phileftrightarrowpsi=phirightarrowpsilandpsirightarrowphi$ is a tautology, i.e. it is always true.

Now, you can check by the semantic evaluation of $rightarrow$ and $land$(the corresponding truth tables), that given an assignment of truth values(an interpretation) $mathcalI$, that $mathcalI(phileftrightarrowpsi)$=1 iff $mathcalI(phi)=mathcalI(psi)$.

share|cite|improve this answer

edited Aug 3 at 14:25

answered Aug 3 at 14:20

zzuussee

1,101419

share|cite|improve this answer

share|cite|improve this answer

edited Aug 3 at 14:25

edited Aug 3 at 14:25

edited Aug 3 at 14:25

answered Aug 3 at 14:20

zzuussee

1,101419

answered Aug 3 at 14:20

zzuussee

1,101419

answered Aug 3 at 14:20

zzuussee

1,101419

1,101419

add a comment | 

add a comment |