Write down the assumptions in a form of clauses and give a resolution proof that the formula is a tautology.  $((p\to q)\land (q\to r)\land p)\to r$  I got information that i need to use here Resolution calculus...Someone can help me?
121673
Write down the assumptions in a form of clauses and give a resolution proof that the proposition                               $$\Big((p \rightarrow q) \land ( q \rightarrow r) \land p \Big) \rightarrow r$$  is a tautology.
43014
Say the following expression is to be proven for all real $x$:     $$|x-1| + |x+1| \geq 2$$   Is it sufficient to just look at the cases where $|x-1|$ and $|x+1|$ are minimum? Or is it necessary to show that the expression it true using other algrebraic manipulations?
90151
I am relatively new to Coq. Can anyone show me how to prove the following in Coq?  (P -&gt; (Q /\ R)) -&gt; (~Q) -&gt; ~P
70069
How do we decide whether the formula in predicate logic is a tautology? Is there some universal way to decide?  Let's have an example:  Vx(P(x)&amp;Q(x))&lt;-&gt;VxP(x)&amp;VxQ(x)   My solution (not correct and not complete)  So the first thing I do is to rename some variables on the right side.   Vx(P(x)&amp;Q(x))&lt;-&gt;VxP(x)&amp;VyQ(y)   No, I can do this:  Vx(P(x)&amp;Q(x))&lt;-&gt;Vx(P(x)&amp;VyQ(y))   And this:  Vx(P(x)&amp;Q(x))&lt;-&gt;VyVx(P(x)&amp;Q(y))   So my question is:   How can I decide and proove, whether it is a tautology?
106123
I am having trouble with a problem in the book I'm self-studying from. It says the following:     Show that $(P\to Q) \land (Q \to R) $ is equivalent to $(P \to R)$   $\land [(P \iff Q) \lor (R \iff Q)]$ by using logical connectives   I have dedicated so far a hefty amount of time on this problem, and now I'm asking you guys advice/hints or solution as to how to solve this problem. Here is one of the methods I used. Point any flaws that I made.  $(P\to Q) \land (Q \to R) $   (Conditional Law)  $(\neg P \lor Q) \land (\neg Q \lor R) \Rightarrow$  (Distributive Law)  $[(\neg P \land \neg Q)] \lor [Q \land (\neg Q \lor R)] \Rightarrow$  (Distributive Law)  $[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Q \land \neg Q) \lor (R \land Q)] \Rightarrow$  Contradiction  $[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Contradiction) \lor (R \land Q)] \Rightarrow$  (Contradiction Law)  $[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [ (R \land Q)] \Rightarrow$  Typically at around step five I get stuck or get confused because the problem gets messy.  I know you could show it by using the truth-tables. However, the problem says use logical connectives. My questions are: Am I on the right track into solving this problem? Did I make any mistakes? What advice/hints would you give me in my path to solving this problem?  Edit Some of you guys want me to list the laws. Here they are:     DeMorgan's laws      $\neg(P \land Q) \equiv \neg P \lor \neg Q$      $\neg(P \lor Q) \equiv \neg P \land \neg Q$      Commutative laws      $P \lor Q \equiv Q \lor P$      $Q\lor P \equiv P \lor Q$      Associative Laws      $P \land (Q \land R) \equiv (P \land Q) \land R  $      $(P \land Q) \land R \equiv P \land (Q \land R)  $      Idempotent Laws      $P \land P \equiv P$      $P \lor P  \equiv P$      Distributive Laws      $P \land (Q \lor R)  \equiv (P \land Q ) \lor (P \land R)$      $P \lor (Q \land R)  \equiv (P \lor Q) \land (P \lor R)$      Absorption Laws      $P \lor (P \land Q) \equiv P$      $P \land (P \lor Q) \equiv P$      Tautology Laws      $P \land (tautology) \equiv P$      $P \lor (tautology) \equiv (tautology)$      Contradiction Laws      $P \land (contradiction) \equiv (contradiction)$      $P \lor (contradiction) \equiv P$      Conditional laws      $P \to Q \equiv  \neg P \lor Q$      $P \to Q \equiv  \neg (P \land \neg Q)$
100562
If we wish to convert a statement of the form $\exists x \in A ~:~ P(x)$ into the form of an implication, would the correct conversion be  $$\exists x ~:~ x \in A \implies P(x)$$  Thanks
105755
I think I have the first part, as I have shown that $q &lt; q + (q'-q)/2 &lt; q'$, but I have trouble in proving that $|q-q'|&lt; \epsilon$.  Could someone tell me if there is a better way of showing the first part and how to show the second part?  For those asking x is a real number
37289
Couple of days back I asked  question. And after reading comments and answer there, even though I knew the definitions of the different terms (tautology, contradiction, contingent, satisfiable, unsatisfiable, valid and invalid) involved, I was quick to realize that I dont know a lot of subtleties, especially connection between these terms. I didnt find one place discussing all these connections. So I spent some time reading comments and answers on that and other linked post and come up with some understanding which I have put below and want your confirmation for it.     First some quick definitions (you may skip this as this super basic. I have put it to avoid any possible ambiguity):         Tautology: a formula that is true in every possible interpretation   Contradiction: a formula that is false in every possible interpretation   Satisifiable: a formula that is true under at least one interpretation   Unsatisfiable: a formula is unsatisifable if it is contradiction   Valid: a formula is valid if and only if it is true under every interpretation   Invalid: a formula is that is false under at least one interpretation      Doubt  Now to get hold of the connection between all these terms. I prepared below figure:    Next as stated in  comment, "Not a typeX" has two meanings: (1) "The negation of a typeX" and "Not a statement that can be categorized as a typeX".   So, with this in mind, I came up with following relations:   $¬$ tautology $=$ $¬$ valid $=$ contradiction $=$ unsatisfiable $¬$ contradiction $=$ $¬$ unsatisfiable $=$ tautology $=$ valid Not a tautology $=$ not a valid $=$ invalid $=$ can be either contradiction or contingent Not a contradiction $=$ not an unsatisfiable $=$ satisfiable $=$ can be either tautology or contingent $¬$ satisfiable $≠$ (unsatisfiable $=$ contradiction) $=$ invalid $=$ can be contradiction or contingent  $¬$ invalid $≠$ (tautology $=$ valid) $=$ satisfiable $=$ can be tautology or contingent Not an invalid $=$ valid $=$ tautology Not a satisfiable $=$ unsatisfiable $=$ contradiction   Above,    $\neg$ means "negation" (or I dont know if it will be more correct or will add more sense if I say a "Boolean negation") "Not a TypeX" means statement "cannot be categorized as TypeX" $=$ simply means "is" $\neq$ simply means "is not"   I know these are pretty much basic stuff but was source of a lot of confusion for me and I wanted all these related things noted down at one place in correct way. Can anyone confirm if above bullet points and figure are correct?
119567
How do I prove $$S\rightarrow \exists xP(x) \vdash \exists x(S\rightarrow P(x))$$ using natural deduction? Just an alignment of which axioms or rules that one could use would be much appreciated.
7756
Problem. Let $(\mathscr{L},\vdash)$ be a logic and $\Gamma\subseteq\mathscr{L}$ be a set of formulas such that for some $\varphi\in\mathscr{L}$ we have $$\Gamma\vdash\varphi\to\neg\varphi$$ $$\Gamma\vdash\neg\varphi\to\varphi$$Then show that, $$\Gamma\vdash(\varphi\to\neg\varphi)\to\varphi$$using only the following, $\color{crimson}{\text{Axiom 1.}}\  P\to (Q\to P)$ $\color{crimson}{\text{Axiom 2.}}\  (S\to (P\to Q))\to((S\to P)\to (S\to Q))$ $\color{crimson}{\text{Axiom 3.}}\  (\neg Q\to\neg P)\to(P\to Q)$ $\color{crimson}{\text{Rule of Inference.}}$ . $\color{crimson}{\text{Theorem.}}$ .  I have tried for some hours to find a proof of the claim but couldn't succeed. Can anyone help?
85556
I am working with Logical Equivalence problems as practice and im getting stuck on this question. Can somebody help?  Im trying to show that The LHS is equivalent to the RHS  (¬P ∧ ¬R) ∨ (P ∧ ¬Q ∧ ¬R) is equivalent to ¬R ∧ (Q ⇒ ¬(P ∧ ¬R))  I have tried this so far:  (¬(P ∨ R) ∨ (¬Q ∧ P ∧ ¬R))  ¬(¬(P ∨ R) ∨ (¬Q ∧ P ∧ ¬R))  (P ∨ R) ∨ (Q ∧ ¬(P ∨ ¬R))  But im unsure how to carry on from here
28448
Here is my proof, I would appreciate it if someone could critique it for me:  To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, then $A⊆B$," and, If $A⊆B$, then $\mathcal{P}(A)⊆ \mathcal{P}(B)$) are true.    Contrapositive of the first statement: If $A \nsubseteq B$, then $\mathcal{P}(A) \nsubseteq \mathcal{P}(B)$  If $A \nsubseteq B$, then there must be some element in $A$, call it $x$, that is not in $B$: $x \in A$, and $x \notin B$. Since $x \in A$, then $\{x\} \in \mathcal{P}(A)$; moreover, since $x \notin B$, then $\{x\} \notin \mathcal{P}(B)$, which proves that, if $A \nsubseteq B$, then $\mathcal{P}(A) \nsubseteq \mathcal{P}(B)$. By proving the contrapositive true, the original proposition must be true.    To prove the second statement true, I would implement nearly the same argument, so that isn't necessary to write. So, does this proof seem correct? Also, was the contrapositive necessary? Or is there another way to prove the initial statement?
42531
We have the following argument: $P \implies Q$ (Premise 1) $P$ (Premise 2) $—$ $∴Q$ (Conclusion)  The accompanying truth table is:    I don't understand this section of my textbook:     The premises are both true only in line four of the table, and in this   line the conclusion is true as well.      You can also see from the truth table that both premises are needed to   make this argument valid. But if we were to change the truth table for   the conditional statement to make P → Q false in the first line of the   table, then the second premise of this argument would no longer be   needed.       We would end up with the conclusion that, just from the single   premise P → Q, we could infer that Q must be true, since in the two   lines of the truth table in which the premise P → Q would still be   true, lines two and four, the conclusion Q is true too.   My thinking:  If we would change the $P → Q$ to be false in the first line of the truth table. Then why couldn't the conclusion be false as well? I don't understand what line $2$ and $4$ have anything to do with line $1$?
13048
I have no idea whether this question is way too specific or whether something similar has already been asked (we still need to work out a way to search for formulas I guess).  Anyways here I go: I want to show that some choice of (logical/quantifier) axioms for a Hilbert derivation system (first order logic, one sort) can prove all the axioms of some other choice.  I have the following at my disposal:  Axioms:   (fot): first order tautologies (i.e. inserting formulas for the propositions in a propositional tautology) (aax): $\forall x A[x] \to A[t]$ (where $t$ is any term and we assume no conflicts with free variables getting bound, $[...]$ denotes replacement)   Inference rules:   (mp): modus ponens (aru): $\frac{A\to B}{A\to\forall x B}$ where $x$ is not free in $A$.   I want to show that this system proves the formula:  $\forall x (A\to B) \to(A \to \forall x B)$ for $x$ not free in $A$ (which I will assume in the following).  This is of course very similar to (aru), but I want this formula, which is of course a stronger statement. I am quite lost here.  Here are my failed attempts: With (aax) and (aru), I easily get the provable rule $\frac{\forall x(A\to B)}{A\to\forall x B}$ which is the formulation of my goal formula as a rule (weaker).  I even get   $$\frac{\bar\forall(A\to B)}{A\to\forall x B}$$ where $\bar\forall$ denotes the universal closure of the following formula.  Using the Deduction Theorem (which I proved for this theory) I get that my system proves $$\bar\forall(A\to B)\to(A\to\forall x B).$$ but that is not exactly what I am looking for.
105983
I have a question for my exam and I find it hard to understand.  I have to prove that the following formula is logically valid:    The professor told me to "push" all the symbols inside the brackets, and use the deduction theorem.  But I don't know how to do it, because I can't find the identities to push the "exist" symbol inside the brackets.  Your help is appriciated, thank you.  Alan
92080
Given two statements, $P$ and $Q$, and the logical connective, $\implies$, the truth table for $P \implies Q$ is:  $$\begin{array}{ c | c || c | }   P &amp; Q &amp; P\Rightarrow Q \\ \hline   \text T &amp; \text T &amp; \text T \\   \text T &amp; \text F &amp; \text F \\   \text F &amp; \text T &amp; \text T \\   \text F &amp; \text F &amp; \text T  \end{array}$$  Lines one and two are quite clear. What is ambiguous is lines three and four.  One explanation as to why $P \implies Q$ is true when $P$ is false, provided by Velleman goes:     Let $P(x)$ be the statement $x&gt;2$ and $Q(x)$, $x^2 &gt; 4$. When $x=3$, $P$ is true, and $Q(x) = 9$ thus $Q$ is true. If $P(x) = 1$ then $Q(x) = 1$ and they are both false. If $P(x) = -3$ then $Q(x) = 9$ and so the statement is true.   This explanation was quite unsatisfactory to me. Looking at Enderton, we have:     For example, we might translate the English sentence, ”If you're telling the truth then I'm a monkey's uncle,” by the formula ($V \implies M$). We assign this formula the value $T$ whenever you are fibbing. In assigning the value $T$, we are certainly not assigning any causal connection between your veracity and any simian features of my nephews or nieces. The sentence in question is a conditional statement. It makes an assertion about my relatives provided a certain condition — that you are telling the truth — is met. Whenever that condition fails, the statement is vacuously true.      Very roughly, we can think of a conditional formula ($p\implies q$) as expressing a promise that if a certain condition is met (viz., that $p$ is true), then q is true. If the condition $p$ turns out not to be met, then the promise stands unbroken, regardless of $q$.   Though a significant improvement over the Velleman explanation, I still feel uncomfortable with it.  Really, it seems we can conjure up as many silly counter-examples as we like, such as:     If pigs can fly, then I can walk on water.   Though following the above truth table, the implication is that my ability to walk on water is true.  After considering it, it seems to me that $\implies$ is only meaningful when $P$ is true, then we can look at it in relation to $Q$. However, if $P$ is false, then we actually know nothing about the relationship between $P$ and $Q$. This would give a truth table of:  $$\begin{array}{ c | c || c | }   P &amp; Q &amp; P\Rightarrow Q \\ \hline   \text T &amp; \text T &amp; \text T \\   \text T &amp; \text F &amp; \text F \\   \text F &amp; \text T &amp; \text ? \\   \text F &amp; \text F &amp; \text ?  \end{array}$$  where the $?$ denotes that given $P$ we actually don't know anything about $ \implies $.  Thus. one way to clear this up would be to assume that $? = T$. Thus the vacuous truth is a "definition of convenience" in a sense.  The above is my take on the matter.  Could someone provide some clarification on the conditional logical connective?
51094
Struggling with this proof, any strategies for natural deduction?  $¬(P \land Q) \vdash ¬P \lor ¬Q$