I wonder whether propositional logic could be formed in all languages. I can imagine some could have problems to construct phrases based on the rules of the logic (e.g. Quechua), but I wonder if there are some, where such "thinking" is not present.
Every natural language has the resources required for constructing a system of propositional calculus, and no language naturally encodes exactly some system of propositional calculus. One fundamental concept of logic corresponds to English "and", which is graphically symbolized in a variety of ways such as ∧ or &. The natural language use of "and" is broader than the formal logical use, which is one reason that logicians like to use separate symbols to keep clear that they are talking just about "∧".
While English has separate words "no, not" corresponding to "~, ¬, ^" etc, negation of a proposition may in natural language be signalled by a particular verb form (a negative inflection). Therefore, translation of a sentence of one natural language into some system of propositional calculus might be more complicated compared to a translation from English. The real difference between English and other languages (Quechua, Zulu, Navaho...) in terms of converting sentences into formal propositions is that there has been a huge amount of work done in discovering the logic-to-language relations of English where they even teach formulaic templates (such as "just in case") with conventional formal logic expressions. Quechua has benefited less from such efforts, but there is no intrinsic linguistic impediment to doing so.