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)

5
votes
4answers
248 views

When $\;\text{FALSE}\implies P(x),\;$ is $P(x)\;$ false?

Say we know that $P(k) \implies P(k+3)$. Then if we know $P(1)$ is true, we know $P(4), P(8) \dots$ are also true. However if we know $P(1)$ is false, does that mean $P(4), P(8) \dots$ are also ...
0
votes
1answer
107 views

non-axiomatizable logics

Hope you're all doing well. My question is about non-axiomatizable logics. My understanding is that a "logic" (the mathematical structure) is just another word for a "propositional calculus" as in ...
0
votes
4answers
85 views

deductions in a propositional calculus

Hope you're all doing well. I have a question about deductions in logical systems. Say we have a logic in the language of propositional logic. We can think of this as the set of tautologies of ...
3
votes
5answers
546 views

Intuition of implication in propositional logic

So, in all the books on propositional logic, I feel unsatisfied with the "intuition" about the meaning of the implication connective. I completely understand how the mechanics work via truth tables, ...
4
votes
2answers
150 views

Cardinality of tautologies for propositional logic

I'm wondering how many tautologies there are in propositional logic. I'm thinking that it must be at least countable, since ($P_{1} \wedge P_{2} \wedge \cdots P_{n}) \models P_{i}$ should be a ...
4
votes
2answers
76 views

A question regarding propositional logic

Good day, I'm currently studying for an exam and need to learn about propositional logic. Well, since I'm not good at English I'll just write what I've done so far: $(A \land (B \rightarrow \neg A)) ...
2
votes
2answers
378 views

Meaning of “strong” and “weak” (formulas?) in propositional logic

I was doing some review of propositional logic from Enderton's book. In one section(pg. 26 of the 2nd edition), he explains the idea that given wffs $\sigma_1, \sigma_2, \cdots, \sigma_k$ and $\tau$, ...
2
votes
1answer
237 views

Axioms and deduction rules of Propositional Calculus

I'm looking for a list of axioms and fundamental deduction rules of Propositional Calculus.
4
votes
2answers
101 views

Sentential Logic

Below is a question comes from the book How to Prove It written by Daniel J. Velleman. Let $P$ stand for the statement, “I will buy the pants” and $S$ for the statement “I will buy the shirt.” ...
0
votes
1answer
84 views

Are These Postulate Sets Interderivable?

One common axiom set for propositional calculus with rule of inference modus ponendo ponens: "From C$\alpha$$\beta$, $\alpha$, we may infer $\beta$", and uniform substitution is: ...
3
votes
2answers
235 views

Converting text to propositional logic

I'm having trouble representing question # 3 in a propositional logic formula, from these lecture notes on propositional logic and propositional resolution: 3) Formalization and Proof. There are ...
0
votes
1answer
57 views

Cardinality of Distinct Hilbert Systems with Detachment

Let us consider all formulas T of classical propositional logic which are tautologies up to simple substitution of variables where a variable can get simply substituted for another variable if and ...
1
vote
1answer
353 views

Propositional Logic and First-Order Logic

I am having a hard time distinguishing between the two different logics. If we consider the statement, “Squares adjacent to the Wumpus are smelly,” and are asked to express it as First-Order Logic, ...
4
votes
1answer
98 views

Some doubts about interpretation of an atomic formula in predicate calculus

I have some doubt related to the interpretation of atomics formulas in predicate calculus. In predicate calculus a formula will be interpreted on a specific domain that is where I take the allowed ...
6
votes
3answers
151 views

Equivalence relation using tableaux

How can I prove that two formulae are equivalent using analytic tableaux? For example, how can I prove the following theorem? $$ (p \rightarrow q) \equiv (\neg q \rightarrow \neg p)$$
0
votes
1answer
106 views

Some doubts about predicate calculus

I am studying the predicate calculus in First Order Logic and I have some doubt about this argument. In my book I find that a formula in the predicate calculus is built from Literals constructed ...
3
votes
0answers
148 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 ...
1
vote
1answer
74 views

Predicate equivalence from Horn clauses?

I have the following Horn clauses (=P): even(n). forall X (even(s(s(X))) <- even(X)). even'(n). forall X (even'(s(s(X)) <- even'(X)). Can I prove one ...
1
vote
3answers
660 views

About NOT elimination/introduction and RAA rules on Natural Deduction

Can somebody explain the $\neg$-elimination rule in natural deduction?. Searching on books and the web, I found different definitions for it. For example, in my logic I course, the rule is: $A, ...
3
votes
3answers
278 views

Proof of $A \lor B, \lnot A\models B$ with natural deduction

Prove that: $A \lor B, \lnot A\models B$ Looks easy but im stuck, and i dont know if to start with an OR elimination or with NOT introduction. Also, different books/texts/etc about Natural ...
2
votes
2answers
993 views

How to apply De Morgan's law?

If for De Morgan's Laws $$( xy'+yz')' = (x'+y)(y'+z)$$ Then what if I add more terms to the expression ... $$(ab'+ac+a'c')' = (a'+b)(a'+c')(a+c)?$$
2
votes
1answer
365 views

“Rules of inference” when the last premise is a conditional?

Another very basic Discrete Mathematics homework problem. I don't want the answer as much as I want to understand the question: Problem 7 For each of the following sets of premises, ...
3
votes
2answers
317 views

Prove p from ¬¬p

I'm stuck on question 2 of these lecture notes on propositional logic: "2. Propositional Proof. Give a formal proof of the sentence p from the single premise ¬¬p using only Modus Ponens and the ...
3
votes
2answers
102 views

Representing $A \rightarrow B$ as $A \supseteq B$ [duplicate]

I know that many people like to think of elementary logic in terms of Venn diagrams, i.e., elementary set theory. I have never found this representation useful, because I can never remember whether ...
2
votes
2answers
382 views

Some doubts about the differences between logic implication and inference rule

I am studying for an Artificial Inteligence university exam that includes a section dedicated to mathematical logic. I am finding some difficulty in understanding the difference between logical ...
3
votes
4answers
223 views

Proving $q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$ using only natural deduction.

I'm trying to prove $$q\Rightarrow r \models (p\land q) \Rightarrow (p \land r)$$ using only the natural deduction rules in this handout. Any hints? I am not allowed to do transformational stuff, ...
0
votes
1answer
36 views

Definition by Recursion and a Question about Induction

I have some questions to ask. Suppose I want to define some sequence of propositional formulas $\{\varphi_{j}\}_{j\in\mathbb{N}}$. First, I define it this way. Fix an enumeration ...
1
vote
1answer
153 views

What law of algebra of proposition is happening here?

I'm preparing for a test tomorrow and going over some reading material, and I came across this problem that was worked out. So far I think I'm following each step of logic, but I've hit a wall with ...
3
votes
2answers
695 views

Proof using natural deduction

Prove that $$\lnot r\Rightarrow \lnot p,\lnot(q\lor r),s\Rightarrow(p\lor q)\models\lnot s $$ I'm completely stuck on this one. Only natural deduction inference rules can be used, no de morgan's law ...
2
votes
3answers
127 views

Proving $(A \land B) \to C$ and $A \to (B \to C)$ are equivalent

Prove that $(A \land B) \rightarrow C$ is equivalent to $A \rightarrow (B \rightarrow C)$ in two ways: by semantics and syntax. Can somebody give hints or answer to solve it?
2
votes
2answers
2k views

De Morgan's laws in natural deduction?

We are asked to use natural deduction to prove some stuff. Problem is, without De Morgan's law, which I think belongs in transformational proof, lots of things seem difficult to prove. Would using de ...
4
votes
3answers
106 views

Trying to understand implication

I'm currently slogging through propositional calculus and making my brain do impressions of a pretzel, but I'm slowly getting it though I'd like to see if that's actually true for the problem below. ...
3
votes
2answers
131 views

Definability of Sets of Truth Assignments

I have some questions about under what conditions a set of truth assignments is the model of some set of sentences. To be more precise, suppose I'm dealing with only propositional logic. Let $K$ be a ...
1
vote
1answer
38 views

Is there some sort of function transformation expressing $(X\implies Y)\Leftrightarrow (\neg X\lor Y)$?

Is there a functional interpretation if the replacement for for the material implication?: $$(X\implies Y)\Leftrightarrow (\neg X\lor Y)$$ Given a function from type $X$ to type $Y$, viewed as a ...
5
votes
2answers
179 views

Which law of logical equivalence says $P\Leftrightarrow Q ≡ (P\lor Q) \Rightarrow(P\land Q)$

I'm going through the exercises in the book Discrete Mathematics with Applications. I'm asked to show that two circuits are equivalent by converting them to boolean expressions and using the laws in ...
0
votes
1answer
358 views

Propositional Logic “Riddle/Puzzle”

I have this kind of 'riddle' as a question that i need to complete, however I'm not sure what to do of it. This is the question: ...
1
vote
1answer
96 views

What does $\vdash s \rightarrow (\neg s\rightarrow t)$ mean?

What does this statement mean $\vdash s \rightarrow (\neg s\rightarrow t)$? And how can I prove it?
0
votes
2answers
1k views

what is the diffrence between a term , constant and variable in first order logic languages ?

in the text , the author says that the language contains parenthises , sentintial connectives and n-place functions , n-place predicates , equality sign = , terms , constans and variables i have two ...
-2
votes
2answers
471 views

How to prove that a set of connectives aren't adequate

I guess we have to prove it somehow by an induction as I saw a few examples online. But it just makes absolutely no sense to me... Can somebody explain it in human language? Thank you very much.
0
votes
1answer
555 views

if $p\implies q$ is the same as $\lnot p \lor q$, then…

If $p\implies q$ is the same as $\lnot p \lor q$, then what is $p\implies \lnot q$? I'm not sure if this is $\lnot p \lor \lnot q$, or $\lnot p \lor q$. I'm trying to figure this out, because i have ...
0
votes
2answers
69 views

Regularity of balanced binary strings

How can one tell which number of propositional variables is necessary to express a Boolean function given as a sequence of 0s and 1s (a binary string) of length $2^n$ as a Boolean formula? ...
1
vote
1answer
44 views

Appearance of sentence parameters in a theorem

Is it true that if $A$ is a formula in a Hilbert system $H$, then if $B_1,B_2,\ldots,B_n$ is a proof of $A$ in $H$, any sentence parameter not appearing in $A$ doesn't appear in $B_1,\ldots,B_n$? If ...
2
votes
2answers
1k views

Is there a difference between 'inconsistent', 'contrary', and 'contradictory'

Is there a difference between 'inconsistent' 'contrary' and 'contradictory'? As far as I understand, two statements are inconsistent when they can not both be true; two statements are contradictory ...
1
vote
1answer
105 views

Implication: F $\implies$ T

Why is F $\implies$ T taken as true? Why is this the "convention"?
3
votes
0answers
59 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 ...
5
votes
2answers
686 views

Deriving A implies B from Not A

My logic textbook has the following example showing how to derive $A \to B$ from $\neg A$: First we assume $A$ and use the conjunction introduction rule which results in a contradiction $[A] \land ...
1
vote
2answers
158 views

Do the premises logically imply the conclusion?

$$b\rightarrow a,\lnot c\rightarrow\lnot a\models\lnot(b\land \lnot c)$$ I have generated an 8 row truth table, separating it into $b\rightarrow a$, $\lnot c\rightarrow\lnot a$ and $\lnot ...
1
vote
4answers
140 views

Writing an expression using logic

Write an expression using letters $\land, \lor, and$ $\neg$ which has the following truth table: $$\begin{array}{ccc|c} P&Q&R&???\\ \hline T&T&T&F\\ T&T&F&T\\ ...
0
votes
3answers
86 views

what is the relation between not A and everything but A

I am examining Bayes' Theorem, and wondering about the alternative interpretations of ~A, as being: not A, ¬ A everything but A, ∀-A And how this will affect the use of probabilities. ...
2
votes
2answers
92 views

Are these propositions equivalent?

Statement 1: Maria will find job if she learns mathematics. Statement 2: Maria will find a job unless she does not learn mathematics. I know the answer is probably that these are same, but ...