Tag Info

New answers tagged

1

It depends a bit how you count / distinguish sets of sentences, If you assume that sets are closed under deduction then there is only one inconsistent set (the set of all sentences) all other sentences are consistent so the chance that you have the inconsistent set is almost nil. If you don't assume closure it is the opposite, every consistent set has ...


3

As you observe, $p\oplus q\oplus r$ is true when only one of the variables is true, or when all three are true. Therefore, $(p\oplus q\oplus r) \wedge \neg(p\wedge q\wedge r)$ would fit your needs.


3

The simplest formula is obviously, $$ ( p \land \lnot q\land \lnot r) \lor ( \lnot p \land \lnot q\land r) \lor ( \lnot p \land q\land \lnot r) $$ Maybe there is a more succinct and elegant formula but I can't seem to unearth it.


1

I'm able to prove it "independently" from the Deduction Theorem, but the proof is quite longer ... The axioms are : $F \rightarrow (G \rightarrow F)$ $(F \rightarrow (G \rightarrow H))\rightarrow ((F \rightarrow G) \rightarrow (F \rightarrow H))$ $(\neg G \rightarrow \neg F) \rightarrow ((\neg G \rightarrow F) \rightarrow G)$ For ...


3

For the non-trivial direction, you're given a model $B$ of the positive consequences of $\Gamma$ and you want an $A$ satisfying two requirements: (1) $A\subseteq B$ and (2) $A$ is a model of $\Gamma$. Notice that requirement (1) can also be phrased as "$A$ is a model of $\Delta$" for a suitable $\Delta$, namely the set of negations of all the sentence ...


3

Here's one way to do it (I think). Starting with $B$, we let $B'\subseteq B$ be a minimal model of the positive consequences of $\Gamma$. $B'$ can be obtained by transfinite recursion (taking intersections at limits). Now, we will show that $B'\vDash \Gamma$. Suppose not; that is, suppose $B'\vDash \neg \phi$ where $\phi$ is a consequence of $\Gamma$. It ...


-3

OTTER has found an 8 condensed detachment, level 5 proof: ----> UNIT CONFLICT at 11.16 sec ----> 26226 [binary,26225.1,2.1] $F. Length of proof is 8. Level of proof is 5. ---------------- PROOF ---------------- 1 [] -P(i(x,y))| -P(x)|P(y). 2 [] -P(i(i(n(a),n(b)),i(b,a))). 3 [] P(i(x,i(y,x))). 4 [] P(i(i(x,i(y,z)),i(i(x,y),i(x,z)))). 5 [] ...


1

The proof must be : 1) $\lnot p \land \lnot q$ --- premise 2) $\lnot p$ --- form 1) by $\land$-elim 3) $\lnot q$ --- form 1) by $\land$-elim 4) $p$ --- assumed [a] 5) $\bot$ --- from 2) and 4) by $\lnot$-elim 6) $q$ --- from 3) and 5) by RAA (or Double negation) 7) $p \rightarrow q$ --- from 4) and 6) by $\rightarrow$-intro, discharging [a] 8) $q$ ...


1

No, that is not correct. I'm assuming it's supposed to be some kind of natural deduction system, but the deductions you annotate with $\neg$elim and $\to$into don't follow any sane negation elimination or implication introduction rules I know. For example you try to conclude $p$ from $\neg p$. That makes no logical sense "Socrates is mortal, ergo Socrates ...


3

I've found a related result into : Jon Barwise (editor), Handbook of mathematical logic (1999), A.2 : H.Jerome Keisler, Fundamentals of Model Theory, page 47-on. See page 72 : 5.10 : Lyndon Homomorphism Theorem (Lyndon [1959]). We can derive from the proof of it the application to the propositional case. Let $\Gamma$ consistent, and let $\Gamma^+$ the ...


0

There is an implied variable in this proposition, namely the day (or hour, etc.) being referred to. The question whether or not this is a tautology therefore does involve quantification over a domain which is potentially infinite, at least in some obvious formalisations. Therefore the question whether the proposition is a tautology is a bit more ...


1

Of course we can "speculate" on philosophy of language issues ad infinitum. BUT ... if we agree that propositional calculus can provide a very very simplified "model" of natural language, suitable for some limited applications, than we have to consider [see Dirk van Dalen, Logic and Structure (5th ed - 2013), page 5] : The linguistic entities occurring ...


0

The automated theorem prover OTTER has found a 10 step, level 5 proof: ----> UNIT CONFLICT at 4.26 sec ----> 11611 [binary,11610.1,2.1] $F. Length of proof is 10. Level of proof is 5. ---------------- PROOF ---------------- 1 [] -P(i(x,y))| -P(x)|P(y). 2 [] -P(i(i(a,b),i(i(b,c),i(a,c)))). 3 [] P(i(x,i(y,x))). 4 [] ...


2

For me, this was one of the most difficult principles in predicate logic to apply, especially in longer proofs with many variables and sub-proofs. To establish the principle involved, I think it really helps to make the domain of quantification explicit for every quantifier as they do in mathematics. Consider the following examples. Example 1 Venturing ...


2

Both statements are not equivalent. As a rule of thumb, in such a sentence, the variables after the $\exists$ symbols depends on every variable declared before. Here, using this rule yields $$ \exists y\ \ \forall x\ \ P(x,y)\\ \forall x\ \ \exists y(\color{red} x)\ \ P(x,y) $$ From here you see that there is no equivalence, but that the first implies the ...


2

They are different statements, in general. The second statement says that for every $x$ there is some $y$ such that $P(x,y)$ holds, while the first states that the same $y$ has $P(x,y)$ hold for every $x$. For example, say we consider the property $x \leq y$, talking about integers. Then $(\forall x)( \exists y)(x \leq y)$ is true - we can take $y = x$. But ...


4

We can formally prove that: $$ \exists y \forall x P(x,y) \implies \forall x \exists y P(x,y) $$ but the reverse implication is not logically valid. Consider the $y$ promised by the first statement, a $y$ which satisfies $P(x,y)$ for every $x$. From this it may be seen that for every $x$, some $y$ exists such that $P(x,y)$. That is the informal ...


0

We have that : $∀xP(x,F_2) \Rightarrow ∃y∀xP(x,y)$ and : $∀xP(x,F_1(x)) \Rightarrow ∀x∃yP(x,y)$. See e.g Skolemization. In both cases the proof is straightforward : 1) $∀xP(x,F_2)$ --- assumed [a] 2) $\exists y \forall x P(x,y)$ --- from 1) by $\exists$-introduction 3) $∀xP(x,F_2) \rightarrow \exists y \forall x P(x,y)$ --- from 1) and ...


0

A number of tableau provers for modal logics at least can be found under http://www.cs.man.ac.uk/~schmidt/tools/ You might be interested in LotREC, Logics Workbench, Mettel (resp. its successor Mettel2) or the Tableau WorkBench. These are generic provers and can be used for many logics, but usually come with calculi for propositional logic (and others) ...


2

If you're willing to prove by truth table: ~ = NOT, <=> = iff p q ~p<=>q ~(p<=>q) T T F F T F T T F T T T F F F F Otherwise We define $\Leftrightarrow$ to be $\neg(x\oplus y)$, where $\oplus$ is $(x\vee y)\wedge \neg(x\wedge y)$. $$\begin{align*}(\neg p\Leftrightarrow ...


2

If your perspective is one of resolution, then it's just an instance of the resolution rule itself. Then $r\implies \neg q$ is an abbreviation for $\neg r\lor \neg q$, and resolution applied to $\neg r\lor\neg q$ and $q$ gives $\neg r$.


3

$r \to \neg q$ is equivalent to $\neg r \lor \neg q$, so given $q$, resolution gives us $\neg r$.


2

1) $( S \land \lnot P ) \lor ( Q \land R )$ --- premise 2) $( S \land \lnot P )$ --- assumed [a] 3) $\lnot P$ --- from 2) by Conjunction elimination (or simplification) 4) $(\lnot P \lor Q)$ --- from 3) by Disjunction introduction 5) $( S \land \lnot P ) \rightarrow (\lnot P \lor Q)$ --- from 2) and 4) by Conditional introduction, discharging [a] ...


0

The first step is to check the hypothesis for eg. $s=0$ and $s=1$ depending on the starting condition. That is, we check if the first two values are odd. Then we assume that $g(s)$ is odd for all $s\in\mathbb{Z}$, where $s\leq k$. This is our induction hypothesis. Like you write, we have \begin{align*} g(k+1)=3\big(g(k)+g(k-1)\big)+1. \end{align*} Can you ...


0

HINT For 1) : if the question is : prove that the argument with premises : $A \Rightarrow (B∨C)$ and $A∨(D∧B)$ and conlcusion : $D \Rightarrow C$ is valid the answer is : NO. Consider a truth assignment $v$ such that : $v(D)=T$ and $v(C)=F$. With this $v$, the conclusion is false. Now it is enough to let : $v(B)=T$ and we have $v(D ...


0

We can prove it in the following way, with some additionsl Lemmas, reffering to : Roger Godement, Algebra [1968 - English translation of Cours d'Algèbre (1963)]. The four logical axioms are those listed above [see page 26-27] and the relation of logical implication : $R \Rightarrow S$ [read : $R$ implies $S$, see page 27] is an abbreviation for : $S$ ...


5

$1)$ $\lnot q$ as premise $2)$ $p$ or $\lnot s$ as premise $3)$ $p \rightarrow$ ($d\land q$) as premise $4)$ $e \rightarrow s$ as premise $5)$ $\quad p\quad$ Assumption $6)$ $\quad d \land q\;$ (3, 5) by modus ponens $7)$ $\quad q\;$ by simplification (6) $8)$ $\quad q \land \lnot q\;$ (1, 8) (And-introduction) $9)$ $\lnot p$, since assumption $p$ ...


1

So somehow you have to show that the disjunct $x_2x_3(\neg x_4)$ is already covered by the expression $x_1x_4 \lor x_1x_2x_3\lor ((\neg x_1)x_3(\neg x_4))$. Since $x_2x_3(\neg x_4)$ is true only when $x_4$ is false, the $x_1x_4$ term won’t come into play, and we should try to get $x_2x_3(\neg x_4)$ out of $x_1x_2x_3\lor ((\neg x_1)x_3(\neg x_4))$. This ...


1

Perhaps this is what you want: $$ ( \neg Q \land \neg R) \lor R = (\neg Q \lor R) \land (\neg R \lor R) $$ Note that $\neg R \lor R$ is always true, so the above becomes: $$\neg Q \lor R.$$


2

Proof : 1) $A → B$ --- premise 2) $C → D$ --- premise 3) $A \lor C$ --- assumed [a] 4) $A$ --- assumed [b] for $\lor$-elimination 5) $B$ --- from 4) and 1) by $\rightarrow$-elimination 6) $B \lor D$ --- from 5) by $\lor$-introduction 7) $C$ --- assumed [c] for $\lor$-elimination 8) $D$ --- from 7) and 2) by $\rightarrow$-elimination 9) $B \lor D$ ...


0

Assume $A\vee C$. Continue by disjunctive syllogism: if $A$ holds, then $B$ holds. If $C$ holds, then $D$ holds. $A\vee C$ holds, so $B\vee D$ holds, and $(A\vee C)\to (B\vee D)$.


0

I'd say that if logic were done to more reflect (useful) mathematical usage the answer would be that such propositions, if atomic, are silly. The silly truth value or values can be thought of as something intermediate between the true and false truth values. If logic is done to make a Heyting prealgebra with an order-reversing involutive negation $\neg$ with ...


0

Using predicate logic with $\in$ as a binary infix relation: $\forall x:[x\in S \iff x\notin x]$ (Premise) $S\in S \iff S\notin S$ (Universal Specification, 1) (a contradiction) $\neg \exists S:\forall x:[x\in S \iff x\notin x]$ (Conclusion, 1, 2) Since $S$ cannot exist, we cannot apply the definition of cardinality (whatever it might be) to $S$, so we ...


1

Your question is essentially a matter of philosophy. Here are some statements about fictional entities that have definite truth values. "A unicorn has one horn." This is true. And the proposition "A unicorn has two horns" is false. Why is this? It's because the definition of a unicorn includes the condition that a unicorn has one horn. We may in fact take ...


5

In normal first-order logic, you cannot refer to something that does not exist. So, for example, you cannot directly say "The cardinality of $S$ is 1." This is because every term, in first-order logic, always refers to an actual object, and so there is no way to make a term for $S$. This is one reason that not every English expression can be translated ...


3

The lesson in Russel's paradox isn't that $S$ doesn't exist, the lesson is that if you accept that you can define such an $S$ you get a contradiction. However, to answer the question in the title, the statement "$\left( \exists x \mbox{ such that } P(x)\right) \implies Q$", or in written language "If (there exists an $x$ such that $P(x)$), then $Q$." is ...


1

See : Greg Restall, Subintuitionistic logic, NDJFL, 35-1 (1994). The system is a subsystem of Intuitionistic Logic. If so, the formula : $(A→B∨C)→((A→B)∨(A→C))$ is not provable, because it is not intuitionistically valid. For a counterexample to the formula, consider the Kripke model with three nodes : $w_0, v_1, v_2$, where $w_0$ is the root ...


1

The formula : (2) $(¬g \lor s_1) \land (¬g \lor s_2) $ is equivalent to [recall that : $p \lor F \equiv p$ and $p \land \lnot p \equiv F$]: $[(¬g \lor s_1) \lor (s_2 \land ¬s_2)] \land [(¬g \lor s_2) \lor (s_1 \land ¬s_1)]$. By Distributive property we have : $(¬g \lor s_1 \lor s_2) \land (¬g \lor s_1 \lor ¬s_2) \land (¬g \lor s_1 \lor s_2) ...


2

So, in propositional logic, each letter symbols (i.e. A and s) should stand for a whole sentence. Notice how s, in your question above, is not an entire sentence. This should be a clue as to what you need to do to solve the problem. You should change your definition of s to a sentence. How do you go about doing this? Notice that the sentence "Students ...


0

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $Here is yet another way to calculate this: $$\calc \lnot Q \lor (\lnot ...


1

$ \newcommand{\calc}{\begin{align} \quad &} \newcommand{\calcop}[2]{\\ #1 \quad & \quad \unicode{x201c}\text{#2}\unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\iff}{\equiv} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}} $One law of logic that is not very well known, ...


1

In your example, you don't start with "¬X∨Z∨¬Y". You start with the set of clauses which has as its members each conjunct of the the conjunction you've listed. If you check your other proofs you'll almost surely find that "¬X∨Z∨¬Y" does not appear anywhere in the proof. If it did, then you would have to have some way to cancel Z or equivalently, you ...


1

We can "dsitribute" the OR in $(A \vee B) \wedge (\neg A \wedge \neg C)$ to get $[A \wedge (\neg A \wedge \neg C)] \vee [B \wedge (\neg A \wedge \neg C)]$ One of the terms should seem supicious.


1

$(A \lor B) \land (\lnot A \land \lnot C) \longleftrightarrow (A \land \lnot A \land \lnot C) \lor (B \land \lnot A \land \lnot C) \longleftrightarrow False \lor (B \land \lnot A \land \lnot C) \longleftrightarrow B \land \lnot A \land \lnot C$


6

$$\begin{align} (A\lor B)\land (\lnot A \land \lnot C) & \equiv [(A\lor B) \land \lnot A] \land \lnot C \\ \\ & \equiv [\underbrace{(A\land \lnot A)}_{\text{False}}\lor (\lnot A \land B)] \land \lnot C \\ \\ & \equiv \lnot A \land B \land \lnot C \end{align}$$ The first equivalence is simply due to the associativity of $\land$. The second is ...


1

See Resolution : The resolution rule is applied to all possible pairs of clauses that contain complementary literals. After each application of the resolution rule, the resulting sentence is simplified by removing repeated literals. If the sentence contains complementary literals, it is discarded (as a tautology). If after applying a resolution rule the ...


1

We have : $$p → ( q → p) \equiv \lnot p \lor (\lnot q \lor p)$$ by Material Implication twice, $$\equiv (\lnot p \lor p) \lor \lnot q$$ by Commutativity and Associativity, $$\equiv (T \lor \lnot q) \equiv T$$ by Negation laws : $p \lor \lnot p \equiv T$ and Identity laws : $T \lor p \equiv T$, $$\equiv T \lor q \equiv (p \lor \lnot p) ...


0

$p\to q$ and $\sim p$ can be substituted with $1+p+pq$ respectively $1+p$, where $pq$ is short for $p\wedge q$ and $+$ is exclusive or. Therefore: $(p\to(q\to p))\equiv 1+p+p(q\to p)\equiv 1+p+p(1+q+qp)\equiv 1+p+p+pq+pqp\equiv 1$, since $r+r\equiv 0$ for all $r$. and $(\sim p\to(p\to q))\equiv ((1+p)\to(1+p+pq))\equiv 1 +(1+p)+(1+p)(1+p+pq)\equiv$ ...


0

Hint: $A\implies B$ is equivalent to $\neg(A\wedge\neg B)$ and also to $\neg A\vee B$. Use De Moivre and transform both formulas in a disjunction of conjunctions.


0

Just look at the possible truth values for (p,q) and check that the two formulas output the same value in the 4 cases. If you want an axiomatic proof you can do this: Since $a\to b$ is a notation for $\neg a\vee b$, we can unfold the first formula into $\neg p\vee (\neg q\vee p)$. This is actually equivalent to $true$, since $p\vee\neg p$ is always true. ...



Top 50 recent answers are included