New answers tagged

1

Think on these lines. $(1)$ All humans die. Equivalent form : For every $x$, if $x$ is human, then $x$ must die. (An implication) $(2)$. Some animals are color blind. Equivalent form: There exists some $x$ such that, $x$ is an animal and $x$ is color blind. (A conjunction)


1

To show that the formula: $(p→q)→((p∨r)→(q∨r))$ is valid with Resolution, we have to consider its negation and show that this is unsatisfiable. Thus, we have to consider: $\lnot [\lnot (\lnot p ∨ q) ∨ (\lnot (p∨r) ∨ (q∨r))]$ i.e. $(\lnot p ∨ q) \land (p∨r) \land \lnot q \land \lnot r)$. Thus, we have the set of clauses: $\{ \{ ¬p,...


1

Let us look at the specific case of two mathmajors. There are the following three possibilities: $\{m,f\},\{m,m\},\{f,f\}$ Of these, only the one outcome would make the phrase "All math majors are male" true, namely where it was $\{m,m\}$. On the other hand, both of the phrases $\{m,f\}$ and $\{f,f\}$ would make the phrase "All math majors are male" ...


1

The negation of a statement $\varphi$, semantically, is a statement $\neg\varphi$ which is true iff $\varphi$ is false. Now in your case, if "all mathematicans are male" is true then "all mathematicans are female" is false. However is in not the case that if "all mathematicians are male" is false, then, all mathematicians are female. Indeed the statement ...


1

"All majors are female" is (one of) the opposite of "All majors are male" The negation of a sentence is another proposition that makes your sentence "look like" false. The way to go is to replace the universal quantifier "All" with its negation "There exist one", and the solutions your professor gave are indeed correct. Think at the sentence "All swans ...


0

Recall that if $p$ and $q$ are propositions, the compound proposition $p \vee q$ can be defined by its truth table. This truth table has $4$ rows, and the truth value of $p \vee q$ will be $F$ only in the row where both $p$ and $q$ have truth value $F$. Similarly, the conditional statement $p \implies q$ is defined to be the proposition $(\sim p) \vee q$...


0

Do a proof by contradiction. Assume that $Atom(\phi)\cap Atom(\psi)=\emptyset$ and prove that we get a contradiction. Let $v_1$ be a valuation such that $v_1(\phi)=T$ (this is possible since $\phi$ is not a contradiction) and $v_2$ be a valuation such that $v_2(\psi)=F$ (this is possible since $\psi$ is not a tautology). Since the atoms of $\psi$ and $\phi$ ...


0

No, modus ponens is not a conjunction. A conjunction consists of a single proposition. Modus ponens has two premises. Also, modus ponens works for implicational propositional calculi where no conjunctions exist. You can substitute a negated formula into an inference rule and obtain a derivable rule of inference provided that you substitute the negated ...


0

With regards to the bulk of your question before your example: The conditional statement asserts asserts that $q$ is true on the condition that $q$ holds, but the statement itself can be wrong. I can say that my statement $r$ is "if I never study ($p$), then I will always get 100% on my exams ($q$)". Then, when I refuse to study and fail the exam, $r$ ...


3

Double-negation introduction: $B\supset \neg\neg B$. You know how to derive $\neg B\supset \neg B$, which is an abbreviation for $\neg\neg B\lor \neg B$. Then A3 gives you $\neg B\lor \neg\neg B$, which is the same as $B\supset \neg\neg B$. Double-negation elimination: $\neg\neg A \supset A$. You know how to derive $A\supset A$, which is just $\neg A\lor A$....


2

You can proceed as follows, it isn't particularly fast though: From $\phi_1$ we know $$R(x,f(x)) \lor R(f(x),f(f(x))) \lor R(x,f(f(x)))$$ for each $x$. From $\phi_4$ we know the last disjunct is impossible, so we know $$R(x,f(x))\lor R(f(x),f(f(x))).$$ From $\phi_2$ if both of those are true then $R(x,f(f(x)))$, again contradicting $\phi_4$ so we know the ...


1

Let $f\colon \mathbb{R} \rightarrow(0,\infty)$ and $a,b\in(0,\infty)$ be given with $a<b$. Suppose $$ \frac{f(a)}{a}<\frac{f(b)}{b}. $$ Then, the above yields $$ \frac{f(a)}{f(b)}<\frac{a}{b}<1. $$ From this it follows that $f(a)<f(b)$. Multiplying both sides of the inequality by $a$ and applying $a<b$ yields $af(a)<af(b)<bf(b)$. ...


2

NOTE: $\sim p$ means "not p", $\sim q$ means "not q". $\sim p \implies \sim q$ is called the inverse of a conditional statement. The inverse is not always true given the original. For example, if $p$ is false and $q$ is true, then we know the original is true because it has a false hypothesis, but the inverse is false because it has a true hypothesis, ...


1

Probably, they should have added at the end of the proof something like 'since $s, t, u$ were arbitrary, the result holds generally for any states.' In other words, they showed that positive introspection is valid on a class of transitive (and hence equivalence) frames. Positive introspection (axiom 4 in usual setting) means that if an agent knows something, ...


0

Multiple like rules work out that we increase the amount assumed in order to get to the derived formula. Generally speaking, it comes as better to derive something from fewer premises than from more premises. Really, the original form comes as bad enough, as often enough you don't need every premise in gamma, you only need a few of those premises to derive ...


1

Your generalized rules are equivalent to the original rules as long as you have the weakening rule (which every reasonable system would have): $\dfrac{Γ \vdash φ}{Γ,Δ \vdash φ}$


2

When the biconditional is legitimate (i.e., when there really is equivalence between the statements), it never hurts to indicate so, and IMO it's always a good idea to use it. This way you can tell if your chain of reasoning is totally reversible, and if it's not reversible, you know which step is the culprit. Even if the result you're trying to establish ...


0

I'm going to try to answer this question although I'm not entirely sure the answer is right. Maybe it will encourage debate, though. I think that the answer is no, you cannot derive this rule without some form of the principle of explosion. My reasoning goes as follows... The premise is a disjunction $p\lor(q\land\neg q)$. I have chosen to arrive at the ...


-1

In Polish notation you might use the rule of inference CN$\alpha$K$\beta$N$\beta$ $\vdash$ $\alpha$ which I'll call No. I'll also use Kol: K$\alpha$$\beta$ $\vdash$ $\alpha$ Kor: K$\alpha$$\beta$ $\vdash$ $\beta$ Ki: $\alpha$, $\beta$ $\vdash$ K$\alpha$$\beta$ and Ao: A$\alpha$$\beta$, C$\alpha$$\gamma$, C$\beta$$\gamma$ $\vdash$ $\gamma$ The proof ...


1

Different authors have called the formula (not the rule) different names. I've seen 'positive paradox', 'simplification', and 'Simp'. I prefer to call the formula [p => (q => p)] or CpCqp in Polish notation, recursive variable prefixing. Why? Because under the the rule of detachment (also called modus ponens) it allows you to prefix any formula with a ...


0

So we have the following rule as a definition of the material conditional, so to speak, at least one way: $$ \frac{p\rightarrow q}{\neg (p\land\neg q)}\quad\text{MaterialConditionalElimation} $$ Now @noah-schweber's comment is that $p\lor\neg q\Rightarrow p\rightarrow q$ rather than $p\lor\neg q\Rightarrow\neg(\neg p\land q)$ which suggests that he ...


3

I believe that "logically entails" and "entails" mean the same thing, here. The point is that in minimal logic, $p\rightarrow q\vdash \neg(p\wedge\neg q)$ is a valid sequent (I'm using "$\vdash$" instead of "$\implies$" here, both for added clarity and to mesh with the standard notation in proof theory). Meanwhile, in intuitionistic logic, $\neg p\vee q\...


5

Yes, $A\to \neg \neg A$ is intuitionistically valid, and your proof looks correct. Many presentations of intuitionistic logic consider $\neg A$ to be an abbreviation for $A\to \bot$, and in that case $A\to\neg\neg A$ is $$ A\to((A\to\bot)\to \bot)$$ which is just an instance of the generally valid $$ A\to((A\to B)\to B) $$


1

Hint We can assume the set of connectives: $\{ \lnot, \land, \lor, \to \}$. We need two preliminary facts: (i) If a formula $F$ is positive (i.e. negation-free), then for any valuation $v$ such that $v(P_i)=$t for all propositional variables $P_i$ occurring in $F$, then $v(F)=$t. Easily proved by Induction on the complexity of the formula [negation-free ...


0

For any wff $\alpha$ Define $\lnot$$\alpha$ as ($\alpha$ $\rightarrow$ 0), where 0 indicates the constant false proposition. Then show that all formulas end up logically equivalent to one with $\rightarrow$ and 0 alone.


3

As some others have pointed out, you used distributivity correctly but in a less than desired way (by complicating the expression further as opposed to simplifying it). As Git Gud notes, you want to "factor out the $\neg p$" where you, instead, expanded things further by distributivity. Finally, you will want to use material implication to simplify your ...


0

Unless the connective $\to$ is defined in terms of $\vee$ and $\neg$, there is no need to go about this proof using the equivalence $p \to q \equiv \neg p \vee q$ or using de Morgan's laws or any of that jazz. You can do it directly. ($\to$) Assume $(p \to q) \wedge (p \to r)$. We'll prove $p \to (q \wedge r)$. To do this, assume $p$; we'll prove $q \wedge ...


2

Remember that a function $f$ from $Y$ to $Z$ takes in an element of $Y$, and spits out an element of $Z$. That is: For each $y\in Y$, there is a unique $z\in Z$ such that $f(y)=z$. The WFF you point to is saying that the predicate $P(y, z)$ behaves in the same way: for each $y$, there is a unique $z$ such that $P(y, z)$ holds.


2

The formula in the second sentence says that for each $y$, there exists a unique $x$ such that $P(y,x)$ is true. This means that you can define a function $f$ by saying that $f(y)$ is the unique $x$ such that $P(y,x)$ is true. This function is essentially equivalent to the formula $P$, since given this function, $P(y,x)$ is equivalent to "$f(y)=x$".


0

I dont know the formal name of the different silogism but you can write $$\forall x(P(x)\implies R(x))\tag{1}$$ To see this clearly you can prove it via "if $x\in P(x)$ then..." and use the notation: $$(A\implies B)\iff(\lnot A\lor B)$$ Then if $\lnot R(a)$ and $(1)$ is true then $\lnot P(a)$ must be true.


-1

If |=($\psi$ eq $\phi$), and ($\Gamma$ $\vdash$ $\psi$), then |=($\psi$ eq $\phi$) and ($\Gamma$ |= $\psi$) by soundness. |=($\psi$ eq $\phi$) implies that |=($\psi$ $\rightarrow$ $\phi$). |=($\psi$ $\rightarrow$ $\phi$) implies ($\psi$ |= $\phi$). Thus can infer that ($\Gamma$ |= $\psi$) and ($\psi$ |= $\phi$). So, we can infer ($\Gamma$ |= $\phi$). ...


0

The trick is to realise that $B\Rightarrow(A\Rightarrow B)$ is a tautology. To see this: Suppose B Hence Suppose A Hence B // because B holds by the outer supposition A=>B B=>(A=>B) I'm not entirely happy with this, because it seems that you are not deriving that B holds by applying any rule whose premises include A, you are ...


1

To avoid circularity, you have to take the "longer way", i.e. enlarge Definition 3.10.4 of Hintikka set to consider all the connectives, and consider all cases in Lemma 3.10.5 and Lemma 3.10.6: it is longer but straightforward. A "standard" approach in many textbook would be: avoiding the shortcut, consider only some "typical" cases (like $\land$, $\lnot$ ...


1

I am assuming that by $=$, you mean logical equivalence, which I will denote by $\equiv$. One thing that might be helpful is the following: For a compound formula $s$, let $s'$ be the formula you get by replacing every variable by its negation. Then, you get the theorem that $s^* \equiv \lnot s'$. Unfortunately, you will need induction on $s$ to prove that:...


0

You have 5 variables to start with, however, 3. Either B or C, but not both are home 4. D and C are either both at home or both not at home These allow you to assume $B = \lnot C$ and $D = C$, so you can reduce the problem to 3 variables, $A, C, E$. 1. If A is at home then so is B 2. Either D or E, or both are at home 5. If E is at home then A and D ...


-1

I use Polish notation. The clauses now read as follows: ANab Ade Abc ANbNc ANdc ANcd ANea ANed To prove any member of {a, Na, b, Nb, c, Nc, d, Nd, e, Ne} we can assume it's complement C. Then if we deduce a contradiction by resolution, the complement of C will have gotten proved. To show that we can't deduce any member of the above set with 8 members ...


1

Your second table is correct. "False" is not a variable, so you can't assign it two different truth values. If the truth table was to be written for a proposition such as $a+b \implies c$, then you would have 8 rows as in the first table. But even then, the first table doesn't look correct. Consider the first row of the table. If $a=F, b=F, c=F$, then $...


2

This is usually formalized just as disjunctions. The initial split is by knowing that $$ t^2=1 \to (t=1 \lor t=-1) $$ and the reasoning within each branch can then be done with metatheorems like $$ (p\to q) \land (p\lor r) \to (q\lor r) $$ So I would say that your $\sqcup$ is simply the good old $\lor$. (In fact, for intuitionistic propositional logic, $\...


1

Either $E$ or $\neg E$. If $E$ then $A\land D$, hence $B\land C$, a contradiction. On the other hand $\neg E$ implies $D$, then $C$, then $\neg B$, then $\neg A$. Since this truth assignment for $A,B,C,D,E$ is compatible with the givens it follows that only $C$ and $D$ are at home.


-1

$G\equiv[(A\land\lnot B)\lor(\lnot A\land B)]$ $====================$ $C\equiv[\lnot B]$ $D\equiv[A\land C]$ $E\equiv[\lnot A]$ $F\equiv[E\land B]$ $G\equiv[D\lor F]$ $\begin{array}{cc|cccc|c} A&B&C&D&E&F&G\\ \hline 0&0&1&0&1&0&0\\ 0&1&0&0&1&1&1\\ 1&0&1&1&0&0&...


3

"False" is not a variable, so you should not add it into the truth table. It makes no sense to say "what if false is true", which is exactly what the second row in your first table asks. Your second table is correct.


0

You must have made an oversight. We can show D is home. If E is home, by 5 so is D. If E is not home, by 2 D is. Then 4 tells us C is home. 3 tells us B is not. 1 tells us A is not. Then 5 tells us E is not. A mechanical approach would be a truth table, though it has $32$ lines. Make one and see which of your clues come out true for each line. ...


1

Together with the proof given in @Hailey's answer, it only remains to show that $\neg P\vee Q$ can be derived from $P\Rightarrow Q$. For this you need the law of the excluded middle. For the proof we have the premise $P\Rightarrow Q$. Now suppose $P$ holds, then by modus ponens and the premise we have that $Q$ holds. From this $\neg P\vee Q$ holds by ...


0

$P\implies Q$ is equivalent to $\neg P ∨Q $ So, $(\neg P ∨ Q )∧\neg Q=(\neg P∧\neg Q )∨(\neg Q ∧ Q)=(\neg P∧\neg Q )\quad$ [As $(Q∧\neg Q)=false$] Now, $\neg Q $ is given that means,it implies $\neg P$


0

Vendor 1 makes two statements which seem to give the answer: "Bad Idea Street will take you to Cold Stone Creamery" [so rule out B.I. St.] "If You’re Lost Avenue leads you to Cold Stone Creamery, then Don’t Even Try It Road will also take you to Cold Stone Creamery" For the second statement to be strictly false, though, the conditional "if" ...


0

It doesn't sound like you're doing it wrong from that description. Each branch ends with a simple proposition. You should then find that the branch contains both a simple proposition and its negation; for example, both $p$ and $\neg p$ appear in the branch. These can be anywhere in the branch, they don't have to be at the end. If you negate the ...


2

Logical formulas like this are always meant to be true, and if what they express is false, so is the formula. That is, the formula you gave essentially says "It is true that there is an x which is p or q", but since the "It is true that..."-part is already part of the semantics of logical formulae away, you wouldn't explicitly spell out this when translating ...


3

Do mathematical if-then statements have anything to do with the classical if-then statements from logic? Yes; they use "the same" if-then. Everything can be proven from the axioms or, more precisely, in a mathematical theory every theorem is proved from the axioms. This amount to: if the axioms are true, then also the theorems are. What ...


0

It really helps me to think about propositions as light bulbs. If a proposition is true, its light bulb is on. If a proposition is false, its light bulb is off. So $p \implies q$ means that whenever $p$ is on, $q$ is on too. If $p$ is off, $q$ could be either on or off. So now let's think about "$p$ only if $q$". If $q$ is off, then $p$ is DEFINITELY off, ...



Top 50 recent answers are included