Questions about truth tables, conjunctive and disjunctive normal forms, negation, and implication of unquantified propositions would fit very nicely under this tag. Questions about other kind of logics should be tagged with [logic] instead.

learn more… | top users | synonyms (1)

4
votes
1answer
185 views

What are those “things that cannot be proved using only ordinary rules of inference”?

The online edition of the book Introduction to Logic by Michael Genesereth and Eric Kao, has a detail that left me confused. CHAPTER 4 [...] 4.2 Linear Proofs [...] The ...
3
votes
1answer
37 views

Prove that ≿ is transitive iff ≻ and ∼ are transitive

Let ≿ be a complete preference relation (as in game theory). How to prove that ≿ is transitive if and only if ≻ and ∼ are both transitive? My reasoning is as follows. ...
3
votes
1answer
82 views

Online tools for checking validity of classical, intuitionistic, … logic formulas?

What online tools are available, where one can enter a formula of (first order) propositional or predicate logic, and have it check whether it is valid classically, intuitionistically, or even ...
3
votes
1answer
123 views

Proving that a propositional theory of any cardinality has an independent set of axioms

This is exercise 1.2.19 from Chang & Keisler's Model Theory, which has been giving me a headache for some time now. Let $\mathscr{S}$ be a given propositional language of any cardinality (i.e. ...
2
votes
1answer
86 views

Equivalence of two very specific propositional calculi

Let $H$ and $L$ be two propositional calculi. $H$ has as inference rule modus ponens only, and three axiom schemes: P1: $A\rightarrow . B\rightarrow A$ P2: $(A\rightarrow . B\rightarrow ...
1
vote
1answer
31 views

Equivalence of two biconditionals of propositional metalogic

In application to propositional metalogic, I am told that the following two biconditionals are equivalent: (i) Γ is satisfiable iff every finite subset of Γ is satisfiable. (ii) Γ ⊨ α iff some ...
1
vote
1answer
54 views

Truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ : What should my next step be?

I am working on a truth table for $(p \implies q) \lor (q \implies r) \lor (r \implies p)$ This is what I have done so far: My next step would be to do the disjunction from the first two ...
1
vote
1answer
97 views

Easy question on Logic and Modes Ponens

I got confused with these: using ONLY this three axioms and Modus Ponens:$$1. \ F \implies (G\implies F) \\ 2. \ (F \implies (G\implies H))\implies ((F \implies G)\implies (F \implies H)) \\ 3. \ ...
1
vote
1answer
70 views

Simplification problem with discrete mathematics

I am trying to achieve this equation: $$x_1x_4 \lor x_1x_2x_3\lor (¬x_1)x_3(¬x_4)$$ I start with: $$(x_1 \lor (¬x_4))(x_3\lor x_4)((¬x_1)\lor x_2\lor x_4)$$ Then I do simplify in the following ...
1
vote
1answer
45 views

Conversion to CNF - eliminate implications

On the web I found a solution to an exercise on resoulution. Basically, it asks to use resolution refutation to prove $$ (P \Rightarrow (Q \Rightarrow R)) \Rightarrow ((P \Rightarrow Q) \Rightarrow (P ...
1
vote
1answer
81 views

How to prove (¬((p→q) → ¬(q→r))) → (p→r) using Lukasiewicz's axioms and MP?

I need a proof for (¬((p→q) → ¬(q→r))) → (p→r) (which is equivalent to (p→q)→((q→r)→(p→r))) using the three axioms and MP: Axiom 1: $A \to (B \to A)$. Axiom 2: $(A \to (B \to C)) \to ((A \to B) \to ...
1
vote
1answer
124 views

Discrete math proof issue

This is a question from my discrete math quiz. I was asked to prove there exists a Q(x). I used Disjunctive Syllogism to prove it. I was marked incorrectly because I used two different variables in ...
1
vote
1answer
443 views

proof of validity of tautology in first order logic

Every first-order logic formula which has a tautological shape in propositional logic is a valid formula. Will it be possible to give a formal proof for the above ? Thanks and Regards.
4
votes
0answers
61 views

(Co)homology of propositional logic

Sorry if this is a rather vague question, but it seemed like something that might be interesting. Let $P$ be a family of propositions, and let $\mathcal L(P)$ be the set of all compound propositions ...
3
votes
0answers
63 views

Is the following derivation of Gödel's Paradox generalizable to an intuitionistic one using provability?

I will follow Goedel's original proof of Goedel's paradox located on pg. 264 of Hao Wang's A Logical Journey: From Gödel to Philosophy. With this in sight, and to also avoid confusion, I will also ...
3
votes
0answers
79 views

Application of the compactness theorem

In my logic book they ask me to prove the following as a consequence of the compactness theorem for propositional logic. Let $S \subseteq N$ be an infinite set. I have to show that there exists an ...
3
votes
0answers
188 views

meaning of ``partial converse''

In the definition of a commutative ring $(R,+,\times)$, one of the postulates given is that of uniqueness, i.e. that $$ a=a', b=b'\implies a+b=a'+b', ab=a' b'.$$ The text states that for the system ...
3
votes
0answers
63 views

Boolean combinatorics

Every finite Boolean algebra has a "middle layer", corresponding to the subsets of size $n/2$ (when looking at the algebra of subsets of $[n]$) or to a set of formulas including $p_i, \neg p_i, p_i ...
3
votes
0answers
330 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of G corresponds to a state q belonging to set Q of the state of the Automaton, for q with $\delta(q,a)=q1*q2$, the node is a $*-node$ ...
2
votes
0answers
30 views

How can i solved this using fitch notation?

I have a little problem that is proof this following statement using fitch notation, can anyone help me out? :) |= (t → s) ∧ ¬((s → q) → (t → q)) Thanks in advance.
2
votes
0answers
77 views

Does There Exist A Fourth Independent Axiom Here?

I use Polish notation. The implicational calculus of propositions under detachment and uniform substitution has the following axioms as a basis: ...
2
votes
0answers
59 views

Expressing schedule of reinforcement rule using mathematical logic

I am trying to formalize the rules for application of different schedules in a reinforcement learning in special education. Children learn through trials. Each trial is successful if the child ...
2
votes
0answers
81 views

Help with propositional logic

Hi all this is for a homework where we just started learning logic and I am not very familiar with propositional logic. So we have two problems: To show a proof of the Sherlock Holmes syllogism ...
1
vote
0answers
70 views

Proving $\vdash (p\to q)\lor (q\to r)$ using natural deduction

I'm trying to prove the following: $\vdash (p\to q)\lor(q\to r)$ using only intuitionistically valid rules. I've tried a few different ways, and I think my problem is that I'm not sure what ...
1
vote
0answers
33 views

Monotonic operators in classical logic

Which means monotony for a logical operator, and affinity, in propositional calculus affinity..., here on wiki do not quite understand!!
1
vote
0answers
30 views

Can the OR function be linearly separated?

I have two questions regarding linear functions and propositional calculus: 1) How do you decide if, for example, the OR function can be linearly separated? The answer is Yes, however I don't know ...
1
vote
0answers
50 views

Dual formula in propositional logic

There's something I don't understand in my course on propositional logic. In the case of x being a variable, the definition of its dual is x* = x. Right. However, further in the course, there's a ...
1
vote
0answers
28 views

Translation into the propositional logic

How could the following sentence be translated into the propositional logic? Since I am here I talk to you. Do I have to use implication like p -> q?
1
vote
0answers
31 views

Validity of Induction Proof - $\{ \land, \top, \bot \}$ is an incomplete set of connectives

I need to verify a proof of the fact that $\{ \land, \top, \bot \}$ is not complete. I consider $\top$ and $\bot$ to be $0$-ary logical connectives that are constantly true or false. That is ...
1
vote
0answers
28 views

Propositonal equivalence and compound proposition

Without using truth tables, show that the statements ‘If you did all problems in the book, attended all lectures and completed all assignments, then you will get an A in Discrete Math’ and ...
1
vote
0answers
354 views

Propisitional logic exam questions and answers

I'm going over exam questions, since my exam is hours away. I'd be extremely grateful if you could check out my answers and evaluate them. Hopefully you guys can see the truth table. Also, i have ...
1
vote
0answers
112 views

Propositional logic truth tables

For the exam that I am taking, propositional always comes up with identical questions. These include writing a sentences in propositional logic, which I can do. But also drawing a truth table for ...
1
vote
0answers
151 views

Relationship between Propositional and First Order Logic

The language of Propositional Calculus comprises of the logical connectives and sentential symbols $A,B,C$ etc. The sentential letters can have arbitrary semantics and truth values. Two wff $\phi$ ...
1
vote
0answers
136 views

Maximally Consistent Set (Proof by Contradiction)

Yesterday, I asked about feedback for a proof of the following theorem For all $\phi$, $\phi \in \Gamma^{*}$ if and only if $\Gamma^{*} \vdash \phi$. My main concern was the first part $(\to)$, which ...
1
vote
0answers
324 views

Inverse function in multi-valued logic through the Webb function

Let Webb function in multi-valued logic as $Webb(x, y) = W(x, y) = Inc(Max(x, y))$. There is a theorem about any function in any multi-valued logic can be represented through the Webb function. Then ...
0
votes
0answers
45 views

Proof verification+proposition

Given 2 function $F(p,v)$ and $\frac{dF}{dv}=g(p,v)$ Differentiate F(p,v) with respect to v give $F_pf+F_v$ Formula 1 $$\frac{dF}{dv}=F_p\left(\frac{dp}{dv}\right)+F_v=g\\ ...
0
votes
0answers
22 views

Construction of atomically closed tableu from a closed tableu

Suppose we have a closed tableu with at least one branch $\theta$ that contains $X$ and $\neg X$ where X is non-atomic formula. My strategy could be that of exploring the cases of X being an ...
0
votes
0answers
64 views

Trying to justify each step correctly in proof sequence

I am trying Justify each step in the proof sequence below for correctly with [A → (B ∨ C)] ∧ B' ∧ C' → A' So I justified my steps here but I am not sure at 1 to 3 if I did it correctly. A → (B ∨ ...
0
votes
0answers
41 views

Proof by contradiction that $P \rightarrow Q$ is true

Let $\tau$ be a closed tableau. Prove that $\tau$ is not satisfiable. So let's say the statement can be expressed by $P \rightarrow Q$. To prove that this statement is true, we look at the assumption ...
0
votes
0answers
34 views

Non Satisfiability of disjuction

Problem: If S1,S2 are (possibly infinite) sets of propositional formulas where their union: S1VS2 is not satisfiable, prove that there exists an ψ such that S1|=ψ and S2|=¬ψ. Can we say that if ...
0
votes
0answers
48 views

Interpretation and truth table is enough to showing validity or a better way?

I'm so glad that find this useful site. anyway, I ran into some challenging ways to find a formula is valid. Here is two example in my note that called valid. I ran into such a problem with making ...
0
votes
0answers
32 views

Formalize “Statement $A$ is the correct explanation of statement $B$”

If I have two statements. Let say Statement $A$ and Statement $B$. What will be the necessary condition or how to write the following conditions mathematically? Statement $A$ is the correct ...
0
votes
0answers
7 views

how many symantec equations is there in propositional calculus with n boolean variables?

how many symantec equations is there in propositional calculus with n boolean variables? The answers are: 1) 3^n 2) n 3) 2^(2n) 4) 2^n I think the answer is 2^n. Do you think its correct? ...
0
votes
0answers
34 views

Performing arithmetical operations (with binary numbers) using propositional logic

Clarifying some terms. By arithmetical operations I mean the four basic operations of addition, subtraction, multiplication and division. By binary numbers I mean numbers in the binary system. By ...
0
votes
0answers
34 views

Expansion Of A algebric term

While doing a coding for software I fell upon in the need to expand the following expression $(A \land B) \land (C \land (D \lor (E \land f)) \land (g \lor h \lor i))$ I tried it and result I got is ...
0
votes
0answers
38 views

proving $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$

I looking for proof of $ (A \rightarrow C) \rightarrow ((A\rightarrow B) \wedge (B\rightarrow C))$ in the foloowing logic (SJ logic in paper of Greg Restall , Subintuitionistic logic) $$⊢A→A$$ ...
0
votes
0answers
34 views

How Do I Show that Condensed Derivable Rules of Inference Yield the Same Formula as Using Condendensed Detachment Multiple Times?

If we look at condensed detachment of two formulas $\alpha$ and $\beta$, we can see that D$\alpha$.$\beta$, where $\alpha$ has form C$\alpha$$_a$$\alpha$$_b$ is equivalent to using the rule ...
0
votes
0answers
31 views

First order logic, equivalence of queries to a database

My book says II should be equivalent to Select R.a,R.b from R,S where R.c=S.c I tried using this page http://en.wikipedia.org/wiki/First-order_logic I got this far. I understand II says for every ...
0
votes
0answers
89 views

Proof of Propositional Compactness Theorem

I am going through the proof for the following form of compactness theorem. Statement: If Φ is an unsatisfiable set of propositional formulas, then some finite subset of Φ is unsatisfiable -- ...
0
votes
0answers
80 views

alternative Compactness theorem proof

I'm attempting a problem which requires me to prove the compactness theorem for propositional logic ![enter image description here][1]in a slightly different way to normal. I'm struggling to ...