# Tag Info

Hint 1: The proofs mainly rely on two basic rules of inference. Conjunction-Elimination ($\wedge{-}$ , $\wedge \rm E$, or similar abreviation ): $\quad A\wedge B \vdash A$ and Disjunction-Introduction ($\vee{+}$, $\vee \rm I$, et cetera): $\quad A\vdash A\vee B$ Plus: Modus Ponens ($\rm MP, \to E$). $\quad A, A\to B\vdash B$ and Modus Tollens ($MT, ... 0 What do you mean by "solve"? If to "solve" something of the form$A \vdash B$means "produce a proof in the formal proof system in My Logic Text from premiss$A$to$B$" (which is the natural reading) then we need to know which text you are using! In this case you have$M \vdash M \lor X$. And it doesn't matter what$X$is, for in any standard logical ... 0 The truth table of a 2-bit gate will have two input columns and two output columns: Input | Output A B | X Y -------+-------- 0 0 | ? ? 0 1 | ? ? 1 0 | ? ? 1 1 | ? ? In order for the gate to be reversible, each output column must contain exactly two ones and two zeroes. This limits the possible output columns to one of ... 1 I also think Sa should be $$\neg (A \land B),$$ or . which includes the event your translation missed that neither Alice nor Bob is in the room. 2 I'm assuming the exercise here asked you to translate the sentences into propositional calculus. Sa should be translated as$\neg (A \wedge B)$; it would have been$A \oplus B$if it had said "Either Alice or Bob are in the room, but not both". For Sb, the more literal translation would be$\neg A \wedge \neg B$, but in classical logic what you wrote is ... 1 " ∼P⇒P⊢P" You can read this as meaning "Suppose that the negation of a proposition implies that proposition. It follows that the proposition is provable." Or equivalently in Polish notation: CNpp$\vdash$p. No one less than Aristotle himself did not understand the law of Clavius. With the principle of bivalence in mind, the only way that the negation ... 2 ''Clavius' law'' is just a variant of proof by contradiction or reductio ad absurdum: If$\sim\! P$implies$P$, then$\sim\! P$is inconsistent (because it then also implies the contradiction$\sim\! P\land P$). Therefore$P$. Formally:$\sim\! P \Rightarrow P\vdash P$. You should be able to formulate any proof by contradiction as an instance of ... 1 Some more examples are $$\sqrt{8}×\sqrt2=\sqrt{16} =4$$ $$\sqrt2×\sqrt{32}=\sqrt{64} =8$$ $$\sqrt5×\sqrt5=\sqrt{25} =5$$ In this way product of two irrational number is rational. 2 As others have mentioned, the main issue here (one that used to bother me as well) concerns operator precedence. As Henning notes, a convention has to be established first for anything to make sense and to avoid ambiguity. Broadly speaking, the following is a little table that lists binary connectives and their corresponding ranks: \begin{array}{ccc} \hline ... 2 It ought to be clear that it's unworkable to allow omitting the parentheses in both$(\neg A)\Rightarrow B$and$\neg(A\Rightarrow B)$. These are two different formulas with different meanings, yet each of them becomes "$\neg A\Rightarrow B$" if we omit the parentheses. Thus, in order to be sure what we're speaking about we need either to declare that ... 3 All of this is a matter of order of operations (or operator precedence). For instance, this is carefully defined in any programming language. From the same wikipedia article: In logic,$\neg$has higher precedence than$\wedge$,$\wedge$higher than$\vee$, and$\vee$higher than$\rightarrow$. 1 I assume that '+' is for '$\vee$' Look at first two terms, and let$A+C=T$: $$(A+C+D)(A+C+D') = (T+D)(T+D') = TT+DT+TD'+DD' = T(T+D+D')+DD' = T(T+1)+DD' = T = A + C.$$ Ok, let's simplify$(A+C)(A+C' + D)$: $$(A+C)(A+C' + D) = (C+A)(C' + (A + D)) = CC' + AC' + C(A+D) + A(A+D) = AC' + C(A+D) + A = (A + AC') + C(A+D) = A + CA + CD = A + CD.$$ And last ... 1 Hint: Simplify bracket by bracket. For example $$(A+C+D)(A+C+D') = AA+AC+AD'+CA+CC+CD'+DA+DC+DD' \\ = A+AC+AD'+CA+C+CD'+DA+DC \\= A+AC+AD'+C+CD'+DA+DC \\= A+AC+C+A(D+D')+C(D+D') \\= A+AC+C+A+C=A+C+AC=A+C$$ Now you can put this expression in the place of the first two brackets and solve again, keeping the rules of simplifying in mind. 2 Your reasoning seems correct. However, I would add that if a set of connectives qualifies as truth-functional complete, that tells us that all functions with the same input and output sets can get computed. A truth-functionally incomplete set of connectives has some functions on the set of truth values which can't get computed. This isn't just about ... 2 There's a related question, which I suspect might be part of what the OP intends to ask: Is "logic without negation" a thing? The answer is yes, in a variety of ways: In intuitionistic logics, we do have the symbol "$\neg$"; however, it does not behave the way we might expect negation to behave. For example, "$\varphi \vee \neg\varphi$" is usually ... 1 In general science, there's a distinction between definitions and axioms that I think is important to recognize. A definition arbitrarily associates a linguistic symbol with an algorithm. Examples include "Let X = 5", "Let Red be 400-484 THz," "Let +(x,y) be the addition algorithm," &c. An axiom is a type of proposition utilizing definitions that is ... 1 More formal proofs exist, but basically: Every atomic predicate always has a negation. If$p$is such a predicate,$\neg p$is the negation. Every logical connective will have a dual; thus every compound predicate has a negation through deMorgan style rules of dual negation. If$\circ, \bullet$are such duals, and$p, q$are predicates, then ... 2 The fact that you can form a negation of every formula is simply a property of the logical language. It will be formally stated as part of the definition of "well-formed formula": Whenever$\varphi$is a formula,$¬(\varphi)$is a formula too. You could consider that an "axiom" (the distinction between axioms and definitions being somewhat fluid) if you ... 0 Yes: given a quantified wff F, there is an algorithm to negate F: you start with the outermost quantifier, negate it, and do so until you are done with the quantifiers. Negation at each point preserves well-formedness. Negations are done like this: 1)~$(\forall x P_{xyz..})$is$\exists x $~P 2)~$(\exists x P_{xyz..})$is$\forall x$~$P_{xyz..}$And ... 3 As per my answer to your previous post , I'll assume that we have available the Deduction Th, that is provable (together with$\vdash A ⇒ A$) from A1) and A2) only. For :$[¬A⇒(¬B⇒C)] \Leftrightarrow [¬(¬A⇒B)⇒C]$, we need some preliminary Lemma : Lemma 1 :$A ⇒ B, B ⇒ C \vdash A ⇒ C$--- Syllogism "derived rule" : easily provable with DT Lemma 2 ... 1 For :$[(A⇒¬B)⇒(A⇒C)]⇒[A⇒(¬B⇒C)]$we assume that we have available the Deduction Th, that is provable (together with$A ⇒ A$) from A1) and A2) only. 1)$[(A⇒¬B)⇒(A⇒C)]$--- assumed [a] 2)$A$--- assumed [b] 3)$¬B$--- assumed [c] 4)$¬B⇒(A⇒¬B)$--- axiom A1) 5)$A⇒¬B$--- from 3) and 4) by Modus Ponens 6)$A⇒C$--- from 1) and 5) by Modus ... 1 Xor is the same as addition modulo 2. Addition you can take in any order. 2 Hints: Denoting XOR by$\Delta$, it would be enough to prove$(a\Delta b)\Delta c=a\Delta(b\Delta c)$, then apply this several times.$a_1\Delta a_2\Delta a_3\Delta\dots\Delta a_n\ $is true iff exactly an odd number of$a_i$'s are true. -2 I have had to flesh out the logic of this myself. (after a late night of studying necessary and sufficient conditions for LSAT purposes, no less. I was a philosophy major and I couldn't just let it be a surface understanding). First, to all you legitimate technicians on this forum (whether by credential or study) if I have made some errors here please ... 2 Let$v_1,\ldots,v_n$be the variables and$\phi(v_1,\ldots,v_n)$an expression in these using only$\land$and$\lor$as connectives. Then we can rewrite this as $$\phi(v_1,\ldots,v_n)\iff v_n\land\phi_1(v_1,\ldots,v_{n-1})\lor \phi_2(v_1,\ldots,v_{n-1})$$ so that we can represent an expression in$n$variables as a pair of expressions in$n-1$variables. ... 4 You are really asking how many different boolean functions of$n$variables can be constructed using$\land$and$\lor$. Assuming you don't allow empty expressions (always true or always false), this is OEIS sequence A007153. 0 First note that $$(\neg p \lor q)\equiv p\rightarrow q$$ So now we have $$(\neg(\neg p \lor q) \lor r) \rightarrow (\neg p \lor (\neg q \lor r))$$ $$\equiv (\neg(p \rightarrow q) \lor r) \rightarrow (\neg p \lor (q \rightarrow r))$$ $$\equiv ((p \rightarrow q) \rightarrow r) \rightarrow ( p \rightarrow (q \rightarrow r))$$ $$\equiv \mbox{tautology}$$ 0 In the referenced List of rules of inferfence, you have the rule for Conditional Introduction (or Conditional proof), that is fundamental to prove a formula with a conditional : 1)$¬(¬p∨q)∨r$--- premise 2)$(¬p∨q) \to r$--- from 1) by Material implication :$(\lnot \varphi \lor \psi) \Leftrightarrow (\varphi \to \psi)$[with :$\lnot p \lor q$as ... 1 You should start supposing the contrary of the conclusion, that is, $$\neg(\neg p \vee (\neg q\vee r)))$$ Now, apply twice the De Morgan's law for$\neg(X\vee Y)$: $$p\wedge q \wedge\neg r$$ Eliminate$\wedge$to obtain$\neg r$. Now, use the premise and eliminate$\vee$: $$\neg(\neg p\vee q)$$ Apply again De Morgan's law: $$p\wedge \neg q$$ Now, eleminate ... 0 [~p^(pvq)]->q [pv(~p^~q)]vq [(pv~p)^(pv~q)]vq [T^(pv~q)]vq (pv~q)vq pvT T ====================== Therefore its a tautology^^ 1 Answer 1: Either$\neg q$or$q$is true. So at least one of$\neg p \vee \neg q$and$p \vee q$is true, so expression 1 is a tautology. Also$\neg q \vee qis always true. so expression 2 is also a tautology, so they are equivalent. Answer 2: \begin{align*} (\neg p \vee \neg q) \vee (p \vee q) &\equiv (\neg p \vee (\neg q \vee (p \vee q)) \\ ... 0 As long as you are using a sound deductive system, to prove\phi\equiv\psi$you have to assume$\phi$then deduce$\psi$from this assumption and assume$\psi$then deduce$\phi$from this assumption. Since a sound deductive system is truth preserving, this ensures that if$\phi$is true then$\psi$is true and if$\psi$is true then$\phi$will be true - ... 2 If with the term tautology you mean also a valid formula of first-order logic, the answer is : YES. In general, we have that :$\forall x \forall y \varphi$and$\forall y \forall x \varphi$are equivalent. Thus,$∀x∀y P(x,y) \to ∀x∀y P(y,x)$is equivalent to$∀x∀y P(x,y) \to ∀y∀x P(y,x)\$. In addition, you can "rename" the bounded variable without ...
Yes, for example you can use DeMorgan's laws: $$a \vee b = \neg((\neg a) \wedge (\neg b))$$ $$a \wedge b = \neg((\neg a) \vee (\neg b))$$ As well as distributivity over the operators: $$a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)$$ $$a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)$$ And there are a lot of more rules you can use to simplify ...