New answers tagged

0

The only possibility that $\neg (r \Rightarrow p) $ is true is that $ \neg p \land r$. For ($q \Rightarrow r$) to be true also, we can take $q$ or $\neg q$, hence $(q \lor \neg q)$. That is also the case for $(p \Rightarrow q)$, since we already have $\neg p$, so we can take $q$ or $\neg q$, hence $(q \vee \neg q)$. Since ($q \lor \neg q$) is always true, we ...


1

Your answer key seems to be writing down the desired statement to be proven before proceeding to prove it, and after that marking it with a tick when done. For example in the case of the second tick the line 2.2 is proven from lines 2.2.1 to 2.2.3. Of course, mathematically it is irrelevant to the formal proof, but in practice it is useful to be able to ...


1

In general, am I allowed to do $(p ∨ (¬p ∧ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))$ Yes, we can.   That is an application of distribution.   Only we don't stop here: were not CNF yet. We can do it again on the first factor: $((p ∨ ¬p) ∧ (p ∨ ¬q)) ∧ (q ∨ (¬p ∧ ¬q))$ But wait: there's a tautology: $(p∨\neg p)$, which can be absorbed (by conjunctive ...


1

You are on the right track, just keep going: \begin{align} (p\wedge q) \vee (\neg p \wedge \neg q) =&\ \big(p \vee (\neg p \wedge \neg q)\big) \wedge \big(q \vee (\neg p \wedge \neg q\big) \\ =&\ \big((p \vee \neg p) \wedge (p \vee \neg q)\big) \wedge \big((q \vee \neg p) \wedge (q \vee \neg q)\big) \\ =&\ (p \vee \neg p) \wedge (p \vee \neg q) ...


0

Note that axiom 1 allows you to get a conditional which has any antecedent you want so long as the consequent is a theorem. For this reason, we can call axiom 1 'recursive variable prefixing.' Axiom 2 we can call 'self-distribution'. Thus, use recursive variable prefixing and self-distribution to deduce (A→A). Use recursive variable prefixing and (A→A) ...


1

Here is an observation that is a little bit too long for a comment: given $f$ and $g$, it is computable whether or not this is possible. We can recursively generate all $m$-ary truth functions that we can make using only $f$ and atoms by the following procedure: start with the set of all atoms; run through the set of all $n$-tuples of truth functions ...


1

For the changed question, about the interpretation of predicate symbols instead of about predicates, in general it is a function from the domain to the collection of truth values. The domain need not be non-empty (that is peculiar to the conventional definition of first-order logic but not always assumed so), and the truth-values may not be two (such as in ...


2

Very very generally, a predicate is something that expects zero or more objects as inputs and produces a truth value as output. Now, of course you have to specify what exactly that means. In particular, in first-order logic here are two possible definitions of predicates (but you cannot choose both!): Simply a (well-formed) formula. The inputs are the ...


1

By Glivenko's Th (6.2.10): $⊢_c \varphi \ ⇔ \ ⊢_i ¬¬ \varphi$. The result follows proving (by Natural Deduction) the intuitionistically valid: $⊢_i ¬ \varphi ↔ ¬¬¬ \varphi$.


1

Always go back to the (intuitive) intended meaning of the logical symbols. "$P \lor Q$" is true exactly when either "$P$" or "$Q$" is true (or both), which is also equivalent to that at least one of "$P$" or "$Q$" is true. Now it is then clear that $( P \lor Q ) \lor R$ is going to be true exactly when at least one of $P,Q,R$ is true, and the order and ...


2

A) 1) $\lnot \lnot \lnot \phi \to \lnot \phi$ --- from $\lnot \lnot \phi \to \phi$ 2) $(\lnot \lnot \lnot \phi \to \lnot \phi) \to (\phi \to \lnot \lnot \phi)$ --- Ax.3 3) $\phi \to \lnot \lnot \phi$ --- from 1) and 2) by modus ponens. B) With Ax.1 and Ax.2 we can easily prove: $\vdash \phi \to \phi$ --- (*). With the Deduction Th we can ...


2

Consider this counterexample: $p:\mathbf{F}$ $q:\mathbf{T}$ Then $$ [(p\to q)\land\neg p]\to\neg q\equiv[(\mathbf{F}\to\mathbf{T})\land\mathbf{T}]\to\mathbf{F}\equiv\mathbf{T}\to\mathbf{F}\equiv\mathbf{F}. $$ How did I come up with this counterexample? Consider the following: \begin{align} [(p\to q)\land\neg p]\to\neg q&\equiv \neg[(\neg p\lor ...


1

The proposition concerned: $$((p\rightarrow q) \land \neg p) \rightarrow \neg q$$ Applying that $\alpha \rightarrow \beta$ is equivalent to $\neg \alpha \lor \beta$, the proposition becomes: $$((\neg p \lor q) \land \neg p) \rightarrow \neg q$$ Applying again: $$\neg((\neg p \lor q) \land \neg p) \lor \neg q$$ Particularly, since we know that it is the ...


2

The LHS always evaluates to TRUE, because whenever the expression to the left of the "implication arrow" is true, $q \lor r$ must be TRUE, and whenever that happens, the expression to the right of the "implication arrow" is also TRUE. On the other hand, the RHS of the full equality is not always TRUE (for all $p$ and $q$). So the equality doesn't hold.


0

If there are not bounds on the method, and you're finding it hard to go with the prepositional boolean algebraic method, then you can go with making truth tables. Since you only have 3 variables here, you just need 8 rows of data, and at most 9 columns to solve it. Compare the columns whose headings are the left, and right hand sides of the equation. If the ...


1

The formula has a free occurrence of the variable symbol $X$. For clarity, we replace the bound occurrences of $X$ by $Z$, so we are looking at the formula $$\forall z(p(Z)\iff q(Z))\land \exists Y(p(Y)\lor q(X)).\tag{1}$$ Some would not assign a truth value to formulas with free occurrences of variable symbols. Some would assign to such a formula the same ...


0

The notation is a bit weird to me. Does 2. announce what you're going to prove? And you need an explicit step introducing $p \land q$ in the system I was taught. The rest seems fine. So in my notation: $(p \land q) \Rightarrow r$ (assumption/axiom) $p$ (assumption) $q$ (assumption) $p \land q$ (from 2 and 3) $r$ (form modus ...


1

I feel a little uncomfortable about throwing in $R$ as an assumption. Assuming $R$ is fine; you discharged that assumption correctly to obtain the desired conditional.   That's exactly what you needed to do. Your actual problem child was properly obtaining the needed consequent, $\neg Q$. Since you can use modus tollens for conditional ...


1

A more compact way of seeing this is simply that $\bot \lor S \iff S$. So $P \Rightarrow S$ is equivalent to $P \Rightarrow (\bot \lor S)$ which is to say $Q$ need not be true if $P \Rightarrow S$ holds (though, of course, $Q$ still could be true).


0

This is just the distributive law in Propositional Logic. https://en.wikipedia.org/wiki/Distributive_property#Propositional_logic


1

Note that $P\implies (Q\vee S)$ is equivalent, as you pointed out, to $(\neg P\vee S)\vee Q$. Thus, to show that $Q$ is true, given only this information, you must show that $(\neg P\vee S)$ is false; i.e., that $P$ is true and $S$ is false. Without any more information, there is not way to conclude for sure that $Q$ is true. If $P$ and $S$ are true, then ...


1

Of course this depends on the definition of "tautology" in predicate logic. The definition I learned years ago is the same as what Wikipedia says: "In the context of predicate logic, many authors define a tautology to be a sentence that can be obtained by taking a tautology of propositional logic and uniformly replacing each propositional variable by a ...


1

An open formula is not possible to evaluate at all. However one often define that $M\models \varphi(x)$ if $M\models \forall x\varphi(x)$. In this case if we translate $\forall x\varphi(x)$ to propositional logic, we only get a single propositional variable $P$ which certainly is not a tautology. So in general I would say No. However a formula such as ...


0

Associativity is a property that applies when you have several operators all the same. So $$ (A \wedge \lnot B) \wedge (B \wedge \lnot A) \equiv (A \wedge \lnot A) \wedge (B \wedge \lnot B). $$ We can apply associativity there because every operator is $\wedge$. (We also have to apply commutativity to get this result.) But $\wedge$ and $\vee$ are different ...


1

The propositions of set theory are consequences of the axioms of set theory, as there are no rules of propositional logic that involve the symbols \epsilon, \cap, \cup. Standard set theory always uses the basic laws of propositional logic in order to make inferences from the set-theoretic axioms.


2

$$\begin{array}{|l|l:l|}\hdashline 1.1&\quad P &\text{A} \\ 1.2&\quad (P \land Q) \rightarrow \neg R &\text{A} \\ 1.3&\quad (P \land ((P \land Q) \rightarrow \neg R) &1.1,1.2\ \land \text{I} \\ \hdashline 2.1&\qquad R \qquad &\text{A} \\ 2.2&\qquad \neg \neg R \rightarrow \neg(P \land Q) &1.2\ \text{MT} \\ ...


1

(A∧B)′ premise (C′∧A)′ premise (C∧B′)′ premise A′∨B′ 1, De Morgan C∨A′ 2, De Morgan C′∨B 3, De Morgan 'A v B 5, 6 resolution 'A 4, 7 resolution


3

Assume that: $[(P∨Q)⇒R]⇒[(P⇒R)∨(Q⇒R)]$ is false. This means: $(P∨Q)⇒R$ true and $(P⇒R)∨(Q⇒R)$ false. Consider the disjunction; a disjunction is false when both disjuncts are; thus: $(P⇒R)$ false and $(Q⇒R)$ false. Now, $P⇒R$ false needs $P$ true and $R$ false, while $Q⇒R$ false needs $Q$ true and $R$ false. Up to now, we have: $P=Q=$t and ...


2

I think you have slightly misunderstood the logical structure of this proof. This is in fact a logically correct proof, albeit I do not think this is the best way to approach a limit proof. It is simply showing that $p\to q$ is logically equivalent to $p\to p$,a tautology. So basically $p\to q$ always has the value $T$ and so we consider the statement ...


2

Consider the following: Let $$ \Omega\equiv\neg(A\land B)\land\neg(\neg C\land A)\land\neg(C\land\neg B)\to\neg A. $$ Your job, then, is to show that $\Omega$ is a tautology: \begin{align} \Omega&\equiv\neg(A\land B)\land\neg(\neg C\land A)\land\neg(C\land\neg B)\to\neg A\tag{by definition}\\[1em] &\equiv (\neg A\lor\neg B)\land(C\lor\neg ...


2

$R \equiv(A'\lor B')\land(C\lor A')\land(C'\lor B) $ $\equiv(A'\lor(B'\land C))\land(B\lor C') $ $\equiv((A'\lor(B'\land C))\land B)\lor ((A'\lor(B'\land C))\land C')$ $\equiv((B\land A')\lor (B\land (B'\land C)) \lor((C'\land A')\lor (C'\land (B'\land C))$ Since $(B\land (B'\land C)) \equiv 0$ and $(C'\land (B'\land C)) \equiv 0$, We have that : $R \equiv ...


1

Good so far. You have shown that $(A \land B)' \land (C' \land A)' \land (C \land B')' \equiv (A' \lor B') \land (C \lor A') \land (C' \lor B)$ You can then write $(A' \lor B') \land (C \lor A') \land (C' \lor B) \equiv (A' \lor B') \land \left [(C \lor A') \land C' \lor (C \lor A') \land B) \right]$ (distributive law) Then consider smaller parts like ...


0

When you are exploring and discovering how to prove a statement, you want to explore by trying to reduce the conclusion to a statement from the hypothesis. That way, you can see how the conclusion is related to the hypothesis and from that connection, write your proof. However, when you are writing your proof, you always start from the hypothesis to the ...


2

"Reaching an obvious truth" (such as $p\to p$ ro $1=1$) is a valif method of proof if the steps used in reaching this obvious truth are equivalence transforms. That is, if your argument goes like $A_1$ is equivalent to $A_2$, which is equivalent to $A_3$, $\ldots$, which is equivalent to $A_n$, which is a tautology then you have proved $A_1$. However, ...


5

Your statement about proof is incorrect. What you state proof isn't is exactly what proof is. What they are doing is showing that the original formula is logically equivalent to a tautology, i.e. to truth. Equivalently, it is enough to show that it is logically implied by a tautology, as then it immediately follows that it is logically equivalent to a ...


0

See my comments, but to rephrase them: We want to be able to find (as in the article linked to) for every given positive number $\epsilon > 0$ (statement $q_{\epsilon}$) at least one positive number $\delta >0$, such that for all positive numbers $\le \delta$ (statements $p_\delta$), the condition involving the given $\epsilon$ is satisfied (i.e. for ...


1

See Liar Paradox : Consider the sentence Liar, which says of itself (i.e., says of Liar) that it is false. (Liar) Liar is false. This seems to lead to contradiction as follows. If the sentence ‘Liar is false’ is true, then Liar is false [because, according to a "reasonable" conception of truth, a sentence S is true iff S corresponds to ...


0

There is a similar, but more detailed answer on quora https://www.quora.com/Does-the-distributivity-of-a-modal-operator-over-disjunction-imply-distribution-over-conjunction/answer/Sebastian-Liu


1

is not a disjunctive clause. In resolution the sentence to be proved must be in conjunctive normal form with the conjuncts represented as elements in a set of clauses. Thus, instead of 3., you must have 3': $P_1$ and 3'': $P_3$. Now, you can conclude with 4: $\lnot P_1 \lor \lnot P_3$.


1

The correct answer is: $\to$ A conditional proposition is an "If antecedent, then consequent" form of statement.   The connective used for this is indeed: $\to$. Statements of equivalence are biconditionals, and the connective used for these is: $\leftrightarrow$


3

The only way I can make sense of "tautological shape" is to suppose a formula $\psi$ is of the form: $$\psi = \alpha[\phi_1 / p_1, \dots,\phi_n/p_n]$$ where $/$ denotes substitution (adequately defined), for some first-order formulas $\phi_i$ and a propositional tautology $\alpha$ in the variables $p_i$. Now let $\mathcal M$ be a structure for $\psi$ and ...


1

Hint : find where the A values are true then find an equation using SOP or sum of products process and then simplify the equation if possible.... Edit : you seem quite new to this so $$A=xyz+x^|yz+x(yz)^|$$ This is how we express in SOP form. You can find such formula for any boolean variable Try to give inputs I.e. x,y and z and find whether you get the ...


0

Take the rows where $A=t$, and OR them: X Y Z A t t t t t f f t f t t t $A=(X \wedge Y \wedge Z) \vee (X \wedge \neg Y \wedge \neg Z) \vee (\neg X \wedge Y \wedge Z)$


2

HINT: Your last paragraph suggests that you do have the right idea about what is wanted. Two propositional formulas are logically equivalent if and only if they have the same truth table. How many different truth tables are possible for a set of $n$ atoms? Each one will represent a whole equivalence class of logically equivalent formulas.


1

The Lemma is indeed true, and your approach is good. I've provided a quite informal proof bellow where I show the induction step which you seem to have trouble with: Assume $\alpha$ is a formula containing $n+1$ connectives from $TC$ and only connectives from $TC$. Write $\alpha$ as $\beta \Delta\gamma$, where $\Delta$ is a connective in $TC$, $\beta$ and ...


2

No, not necessarily. When changing the connective, the modality has to interact with the negation ($p \wedge q \equiv \neg (\neg p \vee \neg q)$), so it may behave differently. The negation may change the modality, $L$ may be changed to a dual modality $K$, with each modality having its own syntactic rules. For example, the exponential in linear logic ...


2

HINT: Prove by induction on the complexity of all well formed propositional expressions $\phi$ that only contain $\rightarrow, \wedge$ as connective symbols that $\phi^* \equiv \text{true}$, where $\phi^*$ results from $\phi$ by assigning $\text{true}$ to each variable in $\phi$. Since $\neg \text{true} \equiv \text{false}$, this implies that $\{ ...


1

Your #1 is certainly not correct, since constructing an $f$ which is not strictly increasing doesn't mean that some other $f$ couldn't be constructed which is strictly increasing. #2 is the correct interpretation. I understand the issue you're having, though. To give a counterexample to a statement $F$ means to give an 'example' showing that $F$ is false, ...



Top 50 recent answers are included